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,3

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.

Links

Robert Israel, Table of n, a(n) for n = 0..10000

Index entries for sequences that are permutations of the natural numbers

Example

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

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

Prog

(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

Crossrefs

Cf. A001045, A065190.

Sequence in context: A309734 A309668 A238758 * A065652 A235200 A267099

Adjacent sequences: A354179 A354180 A354181 * A354183 A354184 A354185

Keyword

nonn,base,changed

Author

Rémy Sigrist, May 18 2022

Status

approved