A163252 a(0) = 0, and a(n) is the least positive integer not occurring earlier in the sequence such that a(n-1) and a(n) differ in only one bit when written in binary.

0, 1, 3, 2, 6, 4, 5, 7, 15, 11, 9, 8, 10, 14, 12, 13, 29, 21, 17, 16, 18, 19, 23, 22, 20, 28, 24, 25, 27, 26, 30, 31, 63, 47, 39, 35, 33, 32, 34, 38, 36, 37, 45, 41, 40, 42, 43, 59, 51, 49, 48, 50, 54, 52, 53, 55, 119, 87, 71, 67, 65, 64, 66, 70, 68, 69, 77, 73, 72, 74, 75, 79, 78

Offset: 0

Author

Keenan Pepper, Jul 23 2009

Keywords

• nonn
• base

Comments

Step from a(488) = 237 = 11101101_2 to a(489) = 749 = 1011101101_2 is the first case when one term is two binary digits longer than the previous. Considering the leading zeros, though, they still differ in only one bit. - Ivan Neretin, Jun 25 2015

Links

• Paul Tek, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A003188, A101080, A360307 (inverse).

Programs

Maple

N:= 10: # to get all terms before the first where a(n) >= 2^N
B:= Array(0..2^N-1):
B[0]:= 1:
a[0]:= 0:
L:= Vector([0$N]):
for n from 1 do
  cands:= select(t -> B[t[1]]=0, [seq(`if`(L[i]=0,[a[n-1]+2^(i-1),i],[a[n-1]-2^(i-1),i]),i=1..N)]);
  if nops(cands)=0 then break fi;
  j:= min[index](map(t->t[1],cands));
  a[n]:= cands[j][1];
  i:= cands[j][2];
  B[a[n]]:= 1;
  L[i]:= 1 - L[i];
od:
seq(a[i],i=0..n-1); # Robert Israel, Jun 25 2015

Mathematica

Nest[Append[#, Min[Complement[BitXor[#[[-1]], 2^Range[0, Floor[Log2[#[[-1]]]] + 2]], #]]] &, {0, 1}, 71] (* Ivan Neretin, Jun 25 2015 *)

Formula

From Alois P. Heinz, Feb 02 2023: (Start)

A101080(a(n),a(n+1)) = 1.

a(A360307(n)) = n = A360307(a(n)). (End)