A354125 - OEIS

%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