Mini-Challenge: Rudin-Shapiro Sequence

[Allen]

@ 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)]