A354125 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.

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, 23, 25, 34, 35, 26, 36, 48, 27, 64, 37, 28, 29, 30, 31, 96, 38, 39, 40, 42, 41, 43, 65, 44, 72, 45, 46, 66, 47, 67, 49, 68, 70, 50, 51, 100, 52, 69, 53, 128, 54, 98

Offset

0,3

Comments

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

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

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

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

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

- for any i = 1..k:

- 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)), ...},

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

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

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

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

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

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

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

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

- 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.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Rémy Sigrist, PARI program

Index entries for sequences that are permutations of the natural numbers

Example

The first terms, alongside the binary expansions of a(n) and a(n + a(n)) are:
  n   a(n)  bin(a(n))  bin(a(n+a(n)))
  --  ----  ---------  --------------
   0     0          0               0
   1     1          1              10
   2     2         10             100
   3     3         11            1000
   4     4        100            1001
   5     5        101            1010
   6     8       1000           10001
   7     6        110           10000
   8     9       1001           10010
   9     7        111           11000
  10    10       1010           10100

Prog

(PARI) See Links section.

Crossrefs

Cf. A354126.

Sequence in context: A356419 A364775 A085176 * A339024 A355429 A192179

Adjacent sequences: A354122 A354123 A354124 * A354126 A354127 A354128

Keyword

nonn,base

Author

Rémy Sigrist, May 18 2022

Status

approved