Nonagintricycles

The story so far: we want to figure out how many unique length-31 cycles and length-93 cycles there are in our second lightpost.

I'll be honest. I didn't know. One of the biggest boons to mathematics has been the advent of the computer, for it allows us to experiment with some mathematical concept, in small to medium sizes. Looking at the small cases might be enough to give us insight if we scale up.

With that in mind, I decided just to enumerate through all the cycles, and then try to explain what I see after the fact. Here they all are:

Each row represents a unique cycle. The red lights are 'on', and the gray lights are 'off'. If you were to take fifteen consecutive lights in one row, and set up the original lightpost to that configuration, then pressing the button would cause the lights to shift once along the cycle.

It is important to note that each row is in fact a cycle: it loops around on itself. This picture would more accurately depict the state of things if it were printed out and wrapped around a cylinder. For our purposes, we need only be aware that if you shifted each pattern once in a direction, and filled in the vacant spot with the value that was 'off the end', you would come up with a different representation of the same cycle. You would not have a new cycle.

What is the answer to the question, then? If you look very carefully, you will find exactly one cycle that is 31 units long; all 352 others are 93 units long. I deliberately hid it by repeating it three times. It is the second-to-last:

Is there a pattern in this data? Maybe. It seems like there is some regular shapes in it, but that may be more a trick of how they are sorted than of any fundamental concept. (For reference, these cycles are ordered by the smallest binary value in the cycle.) Is there perhaps a more 'natural' ordering or grouping that might give us more insight? To begin, I started by counting the number of 'on' lights in each cycle. Doing so, I found three groups: one cycle had 16 lights on; 31 cycles had 32 lights on, and the rest (321) had 48 lights on. This immediately suggested a pattern, for two reasons: multiples of 16 in the number of lights on, and the size of the second group being 31, a number that keeps popping up.

So I took a look at the cycle with 16 lights on:

And at the cycles with 32 lights on:

The first row of the 32-light cycles bears a strong resemblance to the 16-light cycle, and as I looked, the other 32-light cycles seemed to as well. To see the resemblance more clearly, I decided on an arbitrary pattern: five lights, all on, each separated by two other lights, whose state was not important. I then tagged my cycles by highlighting what I call the 'hot bits':

ALL of the 32-light cycles have TWO hot bits. Believing myself to be on the right track, I then rotated each cycle so that one of the two hot bits was in the rightmost position:

Now we're getting somewhere. All of the cycles are identical in 16 columns: the on lights. But a stronger statement is also true, though not as easy to spot: they are also identical in 15 other columns, where they are all off. Sixteen plus fifteen is 31, hmm.

I chose which hot bit to put in the rightmost position arbitrarily. Therefore, my next step was to try choosing the hot bit to align so that the other hot bit had a position that was a multiple of three from the right side:

All of these cycles are now identical in sixty-two columns, or 31 * 2. I did one last operation, to swap the cycles vertically so that they were ordered by their second hot bit:

I daresay we've found a pattern.

We have observed that the number 31 appears over and over as we investigate this lightpost's cycles. An amazing thing happens if we take these cycles, and take from them every third bit. Each cycle will yield three sub-patterns, each 31 units long:

It has become abundantly clear that there is a seed cycle that is growing these patterns:

Finally, the $64,000 question: is this cycle the same as the lightpost's single length-31 cycle?

Damn. Try as you might, you won't be able to rotate one of these two cycles to align with the other. However, they are strongly similar in one sense: if you count the number of runs of lights in the 'on' state, and how many times such a run appears, they match perfectly; the same is true of the runs of lights in the 'off' state. Their only difference is the order of those runs.

Guided by the insights gleaned above, I performed a similar ordering of the remaining 320 cycles containing 48 lights, plus the length-31 cycle. I was not at all surprised to discover that all of these patterns, possessing 48 lights on, each had three hot bits, and that the length-31 cycle has only one hot bit:

This result is a perfect example of why I enjoy recreational mathematics. You will recall that this discussion started with a seemingly-random lightpost, with a button that caused its light pattern to change according to a very simple rule. Despite its simplicity, it actually gives rise to some very rich structure and patterns that have quite pleasing symmetry. Note also a very non-obvious property that is nevertheless guaranteed by how I constructed these images: EVERY fifteen-bit, non-zero can be found in these three images exactly ONCE, if you remember to allow for the number to start at the left and then wrap around and finish at the right.

Join us next time when I explain the origin of the mysterious seed cycle (assuming you haven't already figured out where it comes from), and answer the question that's burning a hole in your brain: just how could any of this have the slightest bearing whatsoever on how the NES and SNES produce audio?