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

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, 5, 14, 7905, 179, 35, 28, 25, 85, 61, 15, 29, 21, 50, 460, 684, 69, 762, 621, 444, 39, 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

Offset

1,1

Comments

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

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').

Links

Table of n, a(n) for n=1..70.

Example

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.
Then the next digit must be 4, and we can indeed choose a(2) = 4 with 2^a(2) = 16.
Then the next digit must be 1, and we can indeed choose a(3) = 1 with 2^a(3) = 2.
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.
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.
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.

Prog

(PARI) {upto(N, d=[], i=1, j=1, U=[])=vector(N, n, my(L=#d, dk, dz, N, F, k);
  while(k++, setsearch(U, k) && next;
   dk = if(k, digits(k), [0]); dz = digits(2^k);
   for( ii = 0, min(L-i, #dk-1), d[ i+ii ] == dk[ 1+ii ] || next(2));
   if ( L >= i + #dk && ! d[i + #dk] && setsearch(U, 0), k = k*10-1; next);
   for( ii = 0, min(L-j, #dz-1), d[ j+ii ] == dz[ 1+ii ] || next(2));
   (N = max ( i + #dk,  j + #dz)-1) > #d && d = Vec(d, N);
   F = i + #dk > j + #dz; for ( ii = L+1, N,
    d[ ii ] = if ( F, dk[ ii-i+1 ], dz[ ii-j+1 ] )); if ( F,
     for ( jj = L+1, j+#dz-1, d[ jj ] == dz[ jj-j+1 ] || next(2)),
     for ( jj = L+1, i+#dk-1, d[ jj ] == dk[ jj-i+1 ] || next(2))); break);
  i += #dk; j += #dz; U=setunion(U, [k]); k)/*+print(d)*/}

Crossrefs

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

Sequence in context: A166905 A278071 A362191 * A132870 A117254 A211022

Adjacent sequences: A362199 A362200 A362201 * A362203 A362204 A362205

Keyword

nonn,base

Author

M. F. Hasler, Apr 10 2023

Status

approved