login
Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of a(n) and a(n + a(n)) have no 1's in common.
2

%I #11 May 22 2022 04:38:54

%S 0,1,2,3,4,5,8,6,9,7,10,11,12,16,17,13,24,18,14,15,20,19,32,21,33,22,

%T 23,25,34,35,26,36,48,27,64,37,28,29,30,31,96,38,39,40,42,41,43,65,44,

%U 72,45,46,66,47,67,49,68,70,50,51,100,52,69,53,128,54,98

%N Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of a(n) and a(n + a(n)) have no 1's in common.

%C This sequence is a permutation of the nonnegative integers with inverse A354126:

%C - the sequence is well defined as we can always extend it with a power of 2,

%C - for any n > 0, let f(n) = n + a(n),

%C - suppose that there are only finitely many integers not in the image of f: say s_1 < ... < s_k,

%C - as the present sequence diverges, for some m > s_k, a(n) > k for any n > m,

%C - for any i = 1..k:

%C - let o_i be the orbit of s_i under repeated applications of f: o_i = {s_k, f(s_k), f(f(s_k)), ...},

%C - let t_i be the least integer > m in the orbit of o_i,

%C - let u = max(t_1, ..., t_k),

%C - the interval I = u+1..u+k contains k terms,

%C - each o_i has at most one element in common with I,

%C - and any orbit o_i containing u has no element in common with I,

%C - so by the pigeonhole principle, some element of I, say w, does not belong to any of the orbits o_i,

%C - so w > s_k does not belong to the image of f, a contradiction,

%C - so there are infinitely many integers not of the form n + a(n),

%C - each time we encounter such an integer, we can extend the sequence with the least unused integer, and eventually every integer will appear in the sequence.

%H Rémy Sigrist, <a href="/A354125/b354125.txt">Table of n, a(n) for n = 0..10000</a>

%H Rémy Sigrist, <a href="/A354125/a354125.gp.txt">PARI program</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e The first terms, alongside the binary expansions of a(n) and a(n + a(n)) are:

%e n a(n) bin(a(n)) bin(a(n+a(n)))

%e -- ---- --------- --------------

%e 0 0 0 0

%e 1 1 1 10

%e 2 2 10 100

%e 3 3 11 1000

%e 4 4 100 1001

%e 5 5 101 1010

%e 6 8 1000 10001

%e 7 6 110 10000

%e 8 9 1001 10010

%e 9 7 111 11000

%e 10 10 1010 10100

%o (PARI) See Links section.

%Y Cf. A354126.

%K nonn,base

%O 0,3

%A _Rémy Sigrist_, May 18 2022