[seqfan] Re: Novel Gray-code-like sequence
C.R. Drost
c.r.drost at gmail.com
Thu Nov 5 22:40:38 CET 2020
Interesting; you've got a sort of undirected graph
0 → 1, 2, 4, 8, 16, 32, 64, ...
1 → 0, 3, 5, 9, 17, 33, 65, ...
2 → 3, 0, 6, 10, 18, 34, 66, ...
3 → 2, 1, 7, 11, 19, 35, 67, ...
4 → 5, 6, 0, 12, 20, 36, 68, ...
5 → 4, 7, 1, 13, 21, 37, 69, ...
6 → 7, 4, 2, 14, 22, 38, 70, ...
plus a sort of “walking rule” through it that steadily burns one-way edges
through the graph as it walks.
Seems like the same principle would work for any sequence of increasing
sequences, but not all of them will be digraphs of course, and one might
wonder which graphs have the property where every edge eventually gets
burned.
Also seems like there is a subtly different sequence where you burn the
nodes rather than the edges,
0 → 1 → 3 → 2 → 6 → 4 → 5 → 7 → 15 → ...
or where you burn the two-way edge rather than the one-way edge,
0 → 1 → 3 → 2 → 0 → 4 → 5 → 1 → 9 → ...
On Thu, Nov 5, 2020 at 10:22 AM Tom Duff <td at pixar.com> wrote:
> It doesn't matter if you're on fresh ground or not. If the sequence is
> not in the OEIS, you should submit it.
> That said, you probably are on new ground.
>
> On Thu, Nov 5, 2020 at 12:57 PM Allan Wechsler <acwacw at gmail.com> wrote:
> >
> > 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.
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list