One interesting Life-like cellular automaton, known as “2×2“, is particularly abundant with frequently-occurring oscillators and has thus attracted some attention from Life enthusiasts over the years. The 2×2 automaton takes place on a grid much like Conway’s Game of Life, but cells are born if they have exactly 3 or 6 neighbours, and they survive if they have exactly 1, 2, or 5 neighbours (this behaviour is summarized by the rulestring “B36/S125”).

Some small period 2 oscillators in B36/S125

Take a look at the second oscillator from the left in the top row of the above image — it is a 2 × 4 rectangle that oscillates back and forth. The oscillators that I will be looking at in this post are rectangles like this; rectangles of sizes 2m × 2n such that m + n is odd (the reason for these restrictions on the sizes of the rectangles is simply that they aren’t oscillators otherwise (not quite, see the correction in the comments)). The next two smallest of these rectangular oscillators are shown here:

Rectangular oscillators in B36/S125

As you can see, the oscillators behave a bit more unpredictably as their size increases. The question that I will answer now is “What is the period of a 2m × 2n rectangular oscillator in the 2×2 rule in terms of m and n?”

I will present the final answer right now, since it isn’t particularly simple: the period is 2^k+1 – 2, where k is the least natural number such that 2^k = ± 1 mod (m + n). While this answer isn’t exactly pretty, the k values have at least already been computed up to m + n = 2001 (see Sloane’s A003558), and there is at least some theory developed about them (see Suborder Function at Mathworld).

It is perhaps worth noting that B36/S125 isn’t the only rule in which these oscillators work; it’s simply the most well-known. These rectangular oscillators behave the same in any rule from B3/S5 to B3678/S012567.

Deriving the Answer

Disclaimer: The following contains much handwaving. It can be made rigorous, but I don’t particularly want to; the argument is long enough as it is, and this is recreational mathematics, after all.

Before proceeding, let’s make a simplification by noticing that a 2m × 2n rectangle is simply another phase of a 2 × 2(m + n – 1) rectangular oscillator. It is thus enough to consider 2 × 4n rectangular oscillators, where n is an integer.

The thing to notice about these oscillators is that, as described by Dean Hickerson in this thread, each phase of these block oscillators can be described as an XOR of rectangles. For example, consider the following phase of one of the above oscillators:

2 × 12 XOR 6 × 8

The above phase can be considered the XOR of a 2 × 12 rectangle and a 6 × 8 rectangle. Different phases may require a different number of rectangles to be XORed, but every phase can always be represented in this way. More important, however, is the fact that the evolution of the oscillators occurs in a very predictable way when modeled like this. Consider the following grid. (Aside: you will likely recognize that it resembles very closely one half of the Sierpinski triangle. This is no coincidence; it turns out that these oscillators are, in a sense, emulating the “Rule 90” 1D cellular automaton.)

XOR grid

The way to read the above grid is that that row represents the current generation and the column represents the size of the rectangle that is being XORed (the first column represents a 2 × 4n rectangle, the second column represents a 4 × (4n – 2) rectangle, the third column represents a 6 × (4n – 4) rectangle, and so on). Thus, you “start” in the top-left cell, and that represents the 2 × 4n rectangle that you start with (in generation 0). To go to generation 1, go to the next row, where we see that the only filled in cell is in the second column, which is the 4 × (4n – 2) column. Thus, the first generation will just be a filled-in 4 × (4n – 2) rectangle. To see what generation 2 will look like, go to the next row, where we see that two cells are filled in, corresponding to 2 × 4n and 6 × (4n – 4) rectangles. Thus, XOR together two rectangles of those sizes (in the sense described earlier) to get what generation 2 must look like.

The key to determining the oscillators’ periods comes from realizing that if we continue to label the columns in the way I described, eventually we hit zero-length rectangles, which doesn’t make a whole lot of sense. Thus, we simply do not XOR any of those rectangles that are of length zero. But what about rectangles of negative length? Instead of counting down into negative numbers, start counting back up. This is probably easiest to illustrate with an example, so I’ll use the n = 3 case.

Coloured XOR grid (n = 3)

Red columns represent 2 × 12, orange represent 4 × 10, yellow represent 6 × 8, green represent 8 × 6, blue represent 10 × 4, purple represent 12 × 2, and grey represent zero-width rectangles that can be ignored. Thus, we see that (for example), in generation 9 (row 10), there is a puple and a green and so the oscillator will look like a 12 × 2 rectangle XORed with an 8 × 6 rectangle.

The period can be determined by grids of this type by going down the rows, looking for the first row (after row 1) that has an odd number of red cells filled in (so that after XORing, a 2 × 4n rectangle will be present) and an even number of each other colour besides grey (so that after XORing, no rectangles of other sizes will be present). It can be shown that the first time this occurs must be at the bottom of one the triangles that reaches all the way to the left (so in row 3, 7, 15, 31, and so on). This corresponds to the oscillators always having period that is equal to 2^k – 2, where k is some integer. To determine what that integer is, notice that if one of these oscillators starts off as a 2 × 4n rectangle, then it will appear rotated 90 degrees as a 4n × 2 rectangle halfway through its period. Thus, we need the least k such that row 2^k-1 contains a single purple cell (i.e., 2^k-1 = ± 1 mod (2n + 1)).

By transforming back to 2m × 2n rectangles and shifting around k a little bit, we see that the period is 2^k+1 – 2, where k is the least integer such that 2^k = ± 1 mod (m + n).

Thus, using Sloane’s A003558 as our guide, we see that the period of a 2m × 2n rectangle for m + n = 3, 5, 7, 9, … is 2, 6, 14, 14, 62, 126, 30, 30, 1022, …

Update [May 28, 2009]: This sequence is now listed in the OEIS as Sloane’s A160657.

Update [January 14, 2019]: A few people (at least Dave Greene as well as wwei and Blinkerspawn in the comments below) noticed that this argument is incorrect — I have just demonstrated an upper bound on the period of these oscillators, and the true period may be a factor of that upper bound (this first happens for the 2-by-72 oscillator, which has period equal to 1/3 of the value claimed in this post). Sequence A160657 has now been updated with the correct values.