login
A362191
Lexicographically earliest sequence of distinct nonnegative integers having the same concatenation of digits as the sequence 2^a(n).
2
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').
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: A360984 A166905 A278071 * A362202 A132870 A117254
KEYWORD
nonn,base
AUTHOR
M. F. Hasler, Apr 10 2023
STATUS
approved