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

0, 1, 2, 5, 4, 3, 10, 9, 8, 7, 6, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61

Offset: 0

Author

Rémy Sigrist, May 18 2022

Keywords

• nonn
• base

Comments

This sequence is a self-inverse permutation of the nonnegative integers.

This sequence has similarities with A065190; here n and n + a(n) have no 1's in common, there they have no common prime factor.

Empirically:

- for n > 0, b(n) = n + a(n) is always a power of 2,

- 2^k appears A001045(k) times in sequence b.

Examples

			The first terms, alongside the binary expansions of n and n + a(n), are:
  n   a(n)  bin(n)  bin(n+a(n))
  --  ----  ------  -----------
   0     0       0            0
   1     1       1           10
   2     2      10          100
   3     5      11         1000
   4     4     100         1000
   5     3     101         1000
   6    10     110        10000
   7     9     111        10000
   8     8    1000        10000
   9     7    1001        10000
  10     6    1010        10000
  11    21    1011       100000
  12    20    1100       100000
  13    19    1101       100000
  14    18    1110       100000
  15    17    1111       100000
  16    16   10000       100000
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A001045, A065190.

Programs

Maple

S:= [$0..100]: R:= NULL:
for n from 0 do
  L:= convert(n,base,2); d:= nops(L);
  found:= false;
  for i from 1 to nops(S) do
    x:= S[i];
    Lx:= convert(n+x,base,2); dx:= nops(Lx);
    if andmap(t -> Lx[t]=0 or L[t] = 0, [$1..min(d,dx)]) then
      found:= true; R:= R,x; S:=subsop(i=NULL,S); break
    fi
  od;
  if not found then break fi
od:
R; # Robert Israel, Jul 14 2024

PARI

s=0; for (n=0, 67, for (v=0, oo, if (!bittest(s,v) && bitand(n, n+v)==0, print1 (v", "); s+=2^v; break)))

Python

from itertools import count, islice
def agen(): # generator of terms
    aset, k, mink = set(), 0, 1
    for n in count(1):
        aset.add(k); yield k; k = mink
        while k in aset or n&(n+k): k += 1
        while mink in aset: mink += 1
print(list(islice(agen(), 68))) # Michael S. Branicky, May 18 2022