Threaded Mode | Linear Mode

John Keith · (This post was last modified: 12-17-2022 06:52 PM by John Keith.)

(12-17-2022 04:03 PM)Allen Wrote: @ 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.

...snip...

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]

Thanks for your interesting observations! I don't think that the patterns you found in the run length are coincidences at all, see my post above in response to ttw. Of course, I don't have a grand unified theory to explain the patterns either. Smile

As it happens, the way I discovered the pattern that led to my HP48G program is by looking at A020987. The Rudin-Shapiro sequence (A020985) is a confusing wall of ones and minus signs but seeing it as a sequence of ones and zeros made the pattern much clearer visually.

One additional note on the subject of run-length encoding: the ListExt commands LRPCT AND LRPC→ perform run-length encoding and decoding respectively. They are very fast.