@ John,
Thank you for an interesting problem!! These challenges are always a good cause to learn more about other areas of math I knew little about. While I was trying to squeeze more juice out of this, I learned some interesting things about the
Shapiro Polynomials and some other items.
One of the potential avenues I explored was using
run length encoding for
A020987. There are some
really interesting properties of this function and these polynomials they represent!!
Regarding the run length, for n up to 2**20 there are no more than 4 0's or 1' in a row. I think it's possible to prove that there are never more than 4 in a row, and
Brillhard and Morton have made a really heavy dent in proving some related theorems- generating 16 pages of math, but without a grand unified proof.
(humorous aside: the authors of this paper say on p.3
"We find ourselves being distracted from the original question by our conjecture, which is interesting in it's own right. Let's indulge ourselves and pursue this pattern question, ignoring the original question for the time being."
The irony of this statement, both in the context of this series, this original forum post, and their paper seems appropriately recursive! In fact, this may be one of the best quotes I've ever seen with respect to applied math research.
Perhaps the second-best math quote I've seen is on p. 15: "
What strange numbers!" - Seems like the kind of thing
Ramanujan or
Erdős, or
Hawking might put on their gravestones.)
For the first 1024*1024, here are the counts of the run lengths:
Code:
0 262144 -> 2**18
2 131072 -> 2**17
3 65536 -> 2**16
1 65536 -> 2**16
This seems a beautiful coincidence!
In the original sequence count for 2**20 is not quite as nice, but close:
Code:
0 524800 -> 2**19 + 2**9
1 523776 -> 2**19 - 2**9
For various reasons, I encoded a run length of 1 as 0 and 2 as 1 and so on, so the first 20 entries of A020987 would be run-length encoded as:
Code:
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1] -> [2, 0, 1, 0, 3, 2, 0, 0, 2, 0]
when packed as binary encoded, the sequence for the first 2*20 A020978 entries fed into
zlib.compress yields only 2791 bytes. Due to the semi-cyclical nature of even the 1X compressed data, feeding those bytes back into zlib again returns only 274 bytes!!
A 500-fold reduction in size (when 2X compressed) can sometimes be a bellwether of deeper mathematical mysteries- or at least some very long repeated sub-sequences.
Behold, 2**20 entries of
A020987 are here:
Code:
789cab98f3f6cac1ac24461196c079d57fff9ff775611174693aa158b2562db9272aecbaaddff19f
16b17ec7dfef9ffef9ebf3dbfff59fbf4ede7e5cbebebef6cfbf3dc79feffff5fbf7e7f9f1efafbe
fefff5effcf8ff779fff7efdfcbfd9ffdde7ffbffcfefdedfbf8fdff97ffb3fffbefebbf2fbfff97
ff9f15ff7dfdf7f53fafffcdfef7ebfcfe2febdfdfb7da7f6fffb3ebff5edbff3ffdcf74ffbefa59
f1bfd7ffcf8529fcbcff6dfce7d7bf97ffdcfaff2b501aa2b4fef6fe67ebfffff1feffeb5fe6bf52
3c66625788d54cecd653e64ea2cd24c19d44fb7d80c39316eea44578d222de4772fa1c2ae13954d2
e750c9ef43257d0e95f01c4d9f23337d8e969fd44e9ffff97f2ffab205001f2570d6
Or I could examine 1 line of python and stop procrastinating my Saturday morning house cleaning:
Code:
A020987_gen=[[x for x in zip(bin(x),bin(x)[1:])].count(('1','1'))%2 for x in range(limit)]