login
Lexicographic earliest sequence of distinct positive integers having the same concatenation of digits as the sequence 2^a(n).
1

%I #9 Jan 25 2024 07:55:38

%S 6,4,1,62,46,11,68,60,18,42,7,3,8,790,470,36,87,44,17,76,64,20,48,2,9,

%T 5,14,7905,179,35,28,25,85,61,15,29,21,50,460,684,69,762,621,444,39,

%U 80,465,1110,41,288,256,65,117,32,84,4609,23,26,89,53,110,52,643,7622,83,175,24,1780,49,13

%N Lexicographic earliest sequence of distinct positive integers having the same concatenation of digits as the sequence 2^a(n).

%C We conjecture that this is a permutation of the positive integers, but a proof seems without reach. Can it be disproved?

%C The sequence greedily extends to infinity, i.e., without backtracking, always choosing a(n) as the smallest possible term compatible with the digits given so far, and not leaving a 0 as next digit to be the initial digit of a future term a(n') or 2^a(n').

%e The first term a(1) must start with the same digits as 2^a(1), the smallest solution is a(1) = 6 with 2^a(1) = 64.

%e Then the next digit must be 4, and we can indeed choose a(2) = 4 with 2^a(2) = 16.

%e Then the next digit must be 1, and we can indeed choose a(3) = 1 with 2^a(3) = 2.

%e Then the next digit must be 6 (last digit of 2^a(2)), but since 6 = a(1) is already used, we have to consider a(4) with at least two digits, the second of which must be 2 from 2^a(3). We can indeed choose a(4) = 62 with 2^a(4) = 4611686018427387904.

%e Then the next digits must be 4 and 6 from 2^a(4). Since 4 = a(2) is already used, we must choose a(5) = 46 with 2^a(5) = 70368744177664.

%e After a(13), the next digits must be 7, 9, and 0. Although 79 is not used earlier, we can't take a(14) = 79, since this would require the next term to start with a digit 0, which is impossible. Therefore, a(14) = 790.

%o (PARI) {upto(N, d=[], i=1, j=1, U=[])=vector(N, n, my(L=#d, dk, dz, N, F, k);

%o while(k++, setsearch(U,k) && next;

%o dk = if(k, digits(k), [0]); dz = digits(2^k);

%o for( ii = 0, min(L-i, #dk-1), d[ i+ii ] == dk[ 1+ii ] || next(2));

%o if ( L >= i + #dk && ! d[i + #dk] && setsearch(U, 0), k = k*10-1; next);

%o for( ii = 0, min(L-j, #dz-1), d[ j+ii ] == dz[ 1+ii ] || next(2));

%o (N = max ( i + #dk, j + #dz)-1) > #d && d = Vec(d, N);

%o F = i + #dk > j + #dz; for ( ii = L+1, N,

%o d[ ii ] = if ( F, dk[ ii-i+1 ], dz[ ii-j+1 ] )); if ( F,

%o for ( jj = L+1, j+#dz-1, d[ jj ] == dz[ jj-j+1 ] || next(2)),

%o for ( jj = L+1, i+#dk-1, d[ jj ] == dk[ jj-i+1 ] || next(2))); break);

%o i += #dk; j += #dz; U=setunion(U, [k]); k)/*+print(d)*/}

%Y Cf. A000079 (2^n), A362191 (variant with nonnegative terms).

%K nonn,base

%O 1,1

%A _M. F. Hasler_, Apr 10 2023