cp's OEIS Frontend

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.

%I A300012 #62 Sep 18 2022 12:38:19
%S A300012 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,
%T A300012 13,26,52,104,208,16,272,136,68,34,17,323,19,57,399,21,483,69,23,115,
%U A300012 575,25,75,225,45,135,27,783,261,87,29,58
%N 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.
%C A300012 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).
%C A300012 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.
%C A300012 "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
%C A300012 From _Peter Munn_, Jun 14 2018: (Start)
%C A300012 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.
%C A300012 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.
%C A300012 (End)
%H A300012 M. F. Hasler, <a href="/A300012/b300012.txt">Table of n, a(n) for n = 1..138</a>
%H A300012 M. F. Hasler, <a href="/A300012/a300012.txt">Table of n, a(n) for n = 1..502</a> (conjectural).
%F A300012 From _M. F. Hasler_, Jun 13 2018: (Start)
%F A300012 For all n, a(n+1)/a(n) is prime or the inverse of a prime (A000040).
%F A300012 Conjecture: A006530(a(n)) <= n; lim sup A006530(a(n))/n < 0.4. (End)
%e A300012 From _M. F. Hasler_, Jun 13 2018: (Start)
%e A300012 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).
%e A300012 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.
%e A300012 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.
%e A300012 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.
%e A300012 A similar situation happens at n = 102 where the value of 258 must be excluded in order to reach 129 at n = 337. (End)
%o A300012 (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))||n<U[1]||denominator(n)>1||(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++); #f<n,i--||break(2)); p=concat([p[1..i-1],n,setminus(Set(p[i..#p]),[n])]);i--); if(try,f[#f-1][1]=f[#f][1]=nextprime(f[#f][1]+1),S,break,f=concat([f,[[2,1]~,[2,-1]~]])));S} \\ Uses the global variable U (used numbers, starting with (smallest unused)-1).
%o A300012 {U=setunion(a=[1],T=[62,258]);S=[31,43]; while(#a<399, a=concat([a,n=find(U[1]+=1,a[#a]), U[1]]); U=setunion(U,Set(n));(n=setsearch(S,U[1]))&& U=setminus(U,[T[n]]); while(#U>1 && 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
%Y A300012 Cf. A006530, A127185.
%K A300012 nonn
%O A300012 1,2
%A A300012 _Peter Munn_, Jun 08 2018