A362191 Lexicographically earliest sequence of distinct nonnegative 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, 79, 0, 470, 36, 87, 44, 17, 76, 64, 20, 48, 2, 9, 5, 14, 790, 51, 793, 52, 82, 58, 56, 115, 29, 21, 50, 460, 684, 69, 762, 621, 444, 39, 80, 465, 1110, 41, 28, 825, 660, 446, 290, 980, 73, 145, 873, 530

Offset

0,1

Comments

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

The sequence extends greedily 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'), once 0 has been used, or of 2^a(n').

Links

Table of n, a(n) for n=0..59.

Example

The first term a(0) must start with the same digits as 2^a(0), the smallest solution is a(0) = 6 with 2^a(0) = 64.
Then the next digit must be 4, and we can indeed choose a(1) = 4 with 2^a(1) = 16.
Then the next digit must be 1, and we can indeed choose a(2) = 1 with 2^a(2) = 2.
Then the next digit must be 6 (last digit of 2^a(1)), but since 6 = a(0) is already used, we have to consider a(3) with at least two digits, the second of which must be 2 from 2^a(2). We can indeed choose a(3) = 62 with 2^a(3) = 4611686018427387904.
Then the next digits must be 4 and 6 from 2^a(3). Since 4 = a(1) is already used, we must choose a(4) = 46 with 2^a(4) = 70368744177664.
Then the next digits must be two 1s, still from 2^a(3). Since 1 = a(2) is already used, we must choose a(5) = 11 with 2^a(5) = 2048.
Then the next digits must be 6 and 8, still from 2^a(3). Since 6 = a(0) is already used, we must choose a(6) = 68 with 2^a(6) = 295147905179352825856.
Then the next digits must be 6 and 0, still from 2^a(3). Since 6 = a(0) is already used, we must choose a(7) = 60 with 2^a(7) = 1152921504606846976.
After a(13) = 79, the next term must start with a digit 0, and we can indeed choose a(14) = 0.
However, thereafter the next three digits must be 4, 7 and 0, and although 47 did not occur earlier, we cannot make this choice since that would require the next term to start with a digit 0, which is now impossible, as 0 already has occurred. Therefore we must choose a(15) = 470.

Prog

(PARI) {upto(N, d = [], i = 1, j = 1, U = [])=vector(N, n, my(L = #d, dk, dz, N, F, k);
  until(!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), A362189 (variant not requiring that terms be distinct), A362202 (variant with positive terms).

Sequence in context: A378418 A166905 A278071 * A362202 A132870 A117254

Adjacent sequences: A362188 A362189 A362190 * A362192 A362193 A362194

Keyword

nonn,base

Author

M. F. Hasler, Apr 10 2023

Status

approved