Rectangular Oscillators in the 2×2 (B36/S125) Cellular Automaton
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”).
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:
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 2k+1 – 2, where k is the least natural number such that 2k = ± 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:
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.)
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.
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 2k – 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 2k-1 contains a single purple cell (i.e., 2k-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 2k+1 – 2, where k is the least integer such that 2k = ± 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.
Thanks for this; I had noticed the pattern but hadn’t worked out the math yet. But when you say “the reason for these restrictions on the sizes of the rectangles is simply that they aren’t oscillators otherwise” that seems to be implying something false. These are definitely not the only rectangular oscillators in this CA. There are also 3×8, 3×16 (=8×11), 4×16 (=8×12), 7×16, 8×16, 3×24 (=8×19=11×16), 3×32 (=4×31=7×28=8×27=16×19), 4×32 (=8×28=16×20), and likely infinitely many others.
It looks like a 3x8n rectangle always has twice the period of a 2x4n one.
Indeed, a (2k-1)x2k+1n rectangle appears to have 2k-1 times the period of a 2x4n one.
I intended for those to be superscripts. It should say a 2^(k-1)x(2^(k+1)n) rectangle has 2^(k-1) times the period of a 2x4n one.
Oops. Wrong again. A (2^k-1)x(2^(k+1)n) rectangle has 2^(k-1) times the period of a 2x4n one. This time it’s right; I checked. 🙂
Whoops, you’re of course right. If you “double” one of these rectangular oscillators, you get a pattern that evolves the same way but takes twice as long to do it. So of course there are the 4×8 oscillator with period 4 and things like that.
This is explained more rigorously (and correctly) in Section 5 of this paper, if you’re interested.
All the best, and thanks for the correction!
This breaks down for n=18, instead of the period being 2^19-2, it’s (2^19-2)/3…
The rectangles composing a Move oscillator can be defined by their corners, which behave as bounded XOR oscillators along the diagonal boundary of the form described in Sloane’s A268754.
Indeed, your A160657 matches the even bisection of that sequence right up until a(18), which was mentioned to be too high by a factor of three by wwei23 above and others.