[seqfan] Newbie discovery

[Ian Hutchinson]

Dear Seqfans,

I recently came up with a sequence that seemed to generate
emergent patterns, which I was fascinated by. I decided to search the OEIS
with the first ~10 terms to see if it was already known, and to my surprise
it returned zero results. This is either because I made a brand new
discovery or because I don't know much about existing sequences, so I
thought I'd get a more knowledgeable opinion on this.

I came up with this while looking for a pattern that would avoid repetition
using simple rules. I came up with a formula in the form of  a(n) =
f(a(n-1), y), where f(x,y) can be any function that receives two integers
and outputs a single value, and y represents the number of terms before
f(n-1) that are equal to f(n-1). This ensures that for any integer k, the
first occurrence of k will be followed by f(k,0), the second will be
followed by f(k,1), the third by f(k,2), and so on. After trying a version
of this with bitxor(x, y) as the main function, I found some intriguing
results.

The first 15 terms are 0, 0, 1, 1, 0, 2, 2, 3, 3, 2, 0, 3, 1, 3, 0, and
already start to reveal an interesting pattern. Terms 1-5 switch between 0
and 1 until the third time 0 shows up, which causes the next term to be 2.
Terms 6-10 switch between 2 and 3 in the exact same way, since there were
no previous occurrences of 2 or 3. Terms 11-15 display a new behavior,
moving all over the range [0, 3] in a less orderly manner, ending after the
5th occurrence of 0. This pattern of repeating everything in a new range
and then creating a more complicated interaction in the combined range
continues at a larger and larger scale, at which point it starts to
generate some striking graphs:
[image: XOR sequence.png]
(This is a plot of the first 3,416 terms, stopping right after the 65th
zero)

I also noticed a few other interesting properties about the resulting
sequence:
- The graph of the first n terms will resemble the graph of the first n/4
terms at sufficiently large values (n>100).
- The behavior of bitxor such that bitxor(n, 0) = n for any integer n
causes an upward sloping line to appear in the top right quadrant of the
above graph, as the series regularly returns to zero and other small
numbers.
- If computed to infinite terms, this sequence may contain every possible
pair of positive integers exactly once. This is based on a few specific
observations that are a little too long to list out here, but I'd be happy
to elaborate on them.

Have any of you seen a sequence like this before? I'm curious to see if the
overall structure of it has been used anywhere else.

Thanks,
Ian