%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