[seqfan] Novel Gray-code-like sequence

Allan Wechsler acwacw at gmail.com
Thu Nov 5 18:13:25 CET 2020


I would have just submitted this, but the idea seems so obvious that I
worried that I would be almost-duplicating an existing concept. So,
colleagues, I appeal to your collective memories and ask if you have seen
this before.

The initial entry is 0.

At each step we toggle one bit of the binary representation of the previous
value.

We always toggle the least significant bit that has never been toggled
before from this value. Thus, though values will be repeated, pairs of
values never will.

>From 0, the smallest bit that has never been toggled is the 1-bit, so we
toggle it and arrive at the second entry, 1.

>From 1, the smallest bit that has never been toggled is also the 1-bit, so
we toggle it, taking us back to 0.

>From 0, we have toggled the 1-bit before, but never the 2-bit, so we go to
2.

If I have made no errors, the sequence begins:

0,1,0,2,3,2,0,4,5,4,6,7,6,4,0,8,9,8,10,11,10,8,12,13,12,14,15,14,12,8,0,...

After the first seven or eight entries OEIS shrugs. I will submit (and
write a program and everything) if your collective wisdom assures me I am
indeed on fresh ground.



More information about the SeqFan mailing list