[seqfan] A simple yet mysterious sequence

[Neil Sloane]

Lexicographically Earliest Sequences like the EKG sequence A064413 have
interested me for years, but are still mysterious. Each of them has a
set-theoretic analog, and these are even more mysterious,

because their graphs all look much the same but are totally unexplained.


Here's the simplest of them, A109812, defined by:

a(1)=1; thereafter a(n) = smallest positive integer not among the earlier
terms of the sequence such that a(n) and a(n-1) have no common 1-bits in
their binary representations.

1, 2, 4, 3, 8, 5, 10, 16, 6, 9, 18, 12, 17, 14, 32, 7, 24, 33, 20, 11, 36,
19, ...


Look at the graph: https://oeis.org/A109812/graph  Look at the bottom
graph, showing 10K terms.

(It looks remarkably like the graphs of A252867, A338833, A352200, A305369,
etc., which have much more complicated definitions.)

I don't even know how to describe these graphs in words. They have a
fractal-like structure, certainly.


So here is my question: A109812 has a really simple definition: Can someone
find a recurrence or generating function, or a Discrete Fourier Transform
(a representation in terms of Walsh functions, perhaps), or any other
explanation for the graph?


The classic Lex. Earliest Seqs. are complicated because they involve
properties of the primes, so that is not a surprise.  But A109812 has
nothing to do with primes. What is going on?


(I'm sending this to the Sequence Fans and Math Fun lists, apologies for
duplicate postings.  But I really want to know the answer.)


Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com