A354125 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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