A300012 A permutation of the positive integers in which adjacent terms differ by a single prime factor and a(n) has no prime factor exceeding prime(n), having the lexicographically earliest inverse.

1, 2, 6, 3, 15, 5, 10, 20, 4, 28, 14, 7, 77, 11, 22, 44, 88, 8, 24, 12, 36, 18, 9, 117, 39, 13, 26, 52, 104, 208, 16, 272, 136, 68, 34, 17, 323, 19, 57, 399, 21, 483, 69, 23, 115, 575, 25, 75, 225, 45, 135, 27, 783, 261, 87, 29, 58

Offset: 1

Author

Peter Munn, Jun 08 2018

Keywords

• nonn

Comments

This permutation can be viewed as a tour of the positive integers, multiplying or dividing by a prime at each step. The "lexicographically earliest inverse" condition means no other such tour visits an integer k earlier, unless it visits an integer less than k later than this tour does (but see the proviso addressed by conjectures 1 and 2 below).

The condition "a(n) has no prime factor exceeding prime(n)" is included to ensure the sequence is well-defined. The author anticipates the condition may be redundant, in the sense that if it is removed: (conjecture 1) the lexicographically earliest inverse remains defined; and (conjecture 2) the terms remain the same.

"Lexicographically earliest inverse" means that the integers 1,2,3,... are reached, in that order, as early as possible. If m is the smallest integer that did not occur up to a given point, the next terms must be chosen as to reach m as early as possible. Among the shortest subsequences leading to m, one must choose the one that has the smallest term(s), unless this prevents reaching a later target in the earliest possible way, cf. Examples of a(63) and a(102). The shortest path from k to m always has either w or w+2 steps (w-1 or w+1 terms between k and m), where w is the number of prime factors of m/k (counted with multiplicity, and negative exponents as positive). - M. F. Hasler, Jun 13 2018

From Peter Munn, Jun 14 2018: (Start)

The calculation of this permutation is in essence derived from the calculation of its inverse, S. When the first k terms of S have been calculated, we can be sure a(S(n)) = n, for n <= k.

However, we are calculating the first k terms of S by calculating a provisional version, P_m, of the first m terms of this sequence and only k of these take the values 1..k that map to the first k terms of S. Of the remaining m - k terms, in the majority of cases P_m(n) can be inferred to be the actual sequence term, a(n), using a short chain of logic. (The usual case: there is only one option for a term P_m(n) that fits with the terms of P_m valued 1..k given the need to multiply or divide by a prime at each step.) Nevertheless, with the exception of a few small values for m, many terms of each P_m are best considered as optional values for the terms of this sequence, to be confirmed -- or replaced by another option -- upon calculating further terms of S using a longer provisional version of this sequence.

(End)

Examples

			From _M. F. Hasler_, Jun 13 2018: (Start)
From a(1) = 1 we reach a(2) = 2 by multiplying by 2. Next we have to reach 3 as early as possible. The fastest way is to multiply by 3 (=> a(3) = 6), then divide by 2 (=> a(4) = 3).
The next target to reach as early as possible is 4. But we cannot divide by a(4) by 5, nor multiply by 2 because 6 has already occurred. We must introduce an additional prime factor to multiply with. It would be possible to use 3, viz. a(4) = 3 -> 3*3 = 9 -> 9*2 = 18 -> 18*2 = 36 -> 36/3 = 12 -> 12/3 = 4 = a(9). However, choosing the larger factor 5 gives a(4) = 3 -> 3*5 = 15 -> 15/3 = 5 -> 5*2 = 10 -> 10*2 = 20 -> 20/5 = 4 = a(9). Here we visit a smaller integer (5) than using the first path, therefore this gives a lexicographically smaller inverse, and is the correct solution.
Similarly, after a(118) = 50, one can reach 51 via (50, 850, 170, 85, 255, 51) or via (50, 150, 2550, 510, 102, 51). The latter comes lexicographically first, but the former fills in the smaller "hole" 85 and is the correct solution.
After a(60) = 30, we can reach the next target, 31, via 30 (*31)-> 930 (/5)-> 186 (/3)-> 62 (/2)-> 31 = a(64), or via 30 (*31)-> 930 (/5)-> 186 (/2)-> 93 (/3)-> 31. The first path seems better because it visits the smaller number 62. However, using 62 here would make it impossible to reach the next target, 32, in only 6 steps (5 multiplications by 2 and one division by 31): since 31 is prime and 1 already used, we must multiply by a larger prime if 31*2 = 62 is used earlier. Therefore the "larger" path via 93 is the correct solution.
A similar situation happens at n = 102 where the value of 258 must be excluded in order to reach 129 at n = 337. (End)
		

Links

• M. F. Hasler, Table of n, a(n) for n = 1..138
• M. F. Hasler, Table of n, a(n) for n = 1..502 (conjectural).

Crossrefs

Cf. A006530, A127185.

Programs

PARI

find(t,s,M=primepi(t)+1)={local(f=Vec(factor(t/s)~), best(a,b)=if(b&&cmp(Set(a),Set(b))>=0,b,a), P(i)=prod(j=1,i,f[p[j]][1]^f[p[j]][2],s),S=[],p); forstep(i=#f,1,-1, while(abs(f[i][2])>1, f=concat(f[1..i], f[i..-1]); f[i][2]-=f[i+1][2]=sign(f[i+1][2]))); while(setsearch(U,prime(M)),M++); #f>1&& for(try=0,M, p=vector(#f,i,i); for(i=1,#p-1,setsearch(U,n=P(i))||n1||(i+1<#p&&next)|| S=best(vector(#p-1,i,P(i)),S); while(n=p[i]+1;while(n<=#f&&(setsearch(Set(p[1..i-1]),n)||f[n]==f[p[i]]),n++); #f1 && U[2]==U[1]+1,U=U[^1]));a} \\ Uses S & T to exclude, e.g., 62 until 31 is reached, cf. Example "After a(60)...". \\ M. F. Hasler, Jun 13 2018

Formula

From M. F. Hasler, Jun 13 2018: (Start)

For all n, a(n+1)/a(n) is prime or the inverse of a prime (A000040).

Conjecture: A006530(a(n)) <= n; lim sup A006530(a(n))/n < 0.4. (End)