When I met my wife 17 years ago, I was interested in a math problem. Here it is:

In a very small grid of cellular automata that wraps around both horizontally and vertically, what’s the longest obtainable sequence of unique patterns?

“Cellular automata” is broad. For the purposes of my problem, I mean a grid with the following features:

1. There are a bunch of squares, like a checkerboard or chessboard. These are called “cells” and each cell can be either alive (or “on”) or dead (or “off”) at any given time. Each cell has eight neighbors; these are the cells that touch it on some edge or at some corner.

   1. Since the grid wraps around horizontally and vertically, a cell on the right edge has some neighbors on the left edge, and a cell on the bottom has some neighbors on the top.

2. The entire grid updates at once, which can be called a step. Each step, cells look around at all their neighbors, and count how many are alive. For certain numbers, the cell will be alive next step. For others, the cell will be dead. Which numbers are which is called a rule.

   1. Unlike in e.g. Conway’s Game of Life, no cell tracks its own state. In other words, a cell can be alive at step n or dead at step n, and this has no influence on whether it’s alive or dead at step n + 1. The only determinant of step n + 1 is how many of its eight neighbors were alive at step n.

Here’s an example 6x6 grid, with two cells highlighted in shades of blue, and their neighbors highlighted in red and orange:

The rule for this grid is: if a cell has 3 or 4 neighbors currently alive, it will be alive next turn. If it has any other number of alive neighbors, it will be dead. The light blue cell clearly has 3 alive neighbors, so it will be on next turn. The dark blue cell might appear at a glance to have 4 alive neighbors, but actually it has 5, so it will be off next turn. To see why the pink cell is one of its neighbors, consider starting with the dark blue cell, then going one to the right (thus ending up on the left edge) then one up. That’s a single diagonal step, so it’s a neighbor, and the dark blue cell will be off.

Here’s what the grid looks like without color coding (black cells are alive):

Here’s what the entire grid will look like on the next step; check a few random cells that are alive and verify that they had exactly 3 or 4 alive neighbors before:

Finally, here’s a gif showing all the steps from then on, until the grid stabilizes and doesn’t change anymore.

Eventually, since these grids are finite and only have so many possible states, you have to repeat the same pattern twice. Moreover, since they’re totally deterministic, once a pattern repeats, that configuration will have the same next configuration as the last time it showed up, creating an infinite loop.

In theory, a grid with n cells can have 2^n different configurations, so a rule that hit every single possible configuration could last up to 2^n steps before repeating itself. But in fact no rule does this, or even comes close, for small grids.

In fact, we can prove it. Let’s start with 3x3.

First, a silly observation: in a three by three grid, every cell is every other cell’s neighbor. This is extra obvious for the “middle” cell:

But since the grid wraps around, it’s just the same for the other cells. For example:

From here, we can make a fun observation: all the living cells have the same number of living neighbors as each other, and all the dead cells do too! If 5 cells are alive, then every living cell has 4 living neighbors (since no cell is its own neighbor), and every dead cell has 5 living neighbors.

Because it’s so cramped, you can’t get too many different patterns in a 3x3 grid. Every living cell can either stay alive, or die at once, and every dead cell can either stay dead, or come to life at once. The only real options are repeated inversion:

Or the entire grid turning either alive or dead:

Since these are the only available transformations, the longest possible sequence simply chains both together. You pick a start configuration that will invert, then turn the whole grid alive, then turn the whole grid dead. (Or invert, then turn all dead, then turn all alive; it doesn’t matter which. It also doesn’t matter if the grid stays the exact same after its fourth state, or flashes between all dead and all alive forever.)

For example, let’s consider the following start configuration and rule:

First, the cells that are alive die (since each has 4 living neighbors), and the cells that are dead come to life (since each has 5 living neighbors):

Now no cell has 0 or 5 living neighbors; the living cells have 3 and the dead cells have 4. So the entire grid will turn off:

Now every cell has 0 living neighbors, so they all turn on:

At this point, the grid will just loop between all on and all off, but that doesn’t matter. Our core question isn’t about the loop itself, but how many unique configurations we can get before we see one we’ve seen before. In this case, we saw four. Here they all are together.

You cannot possibly have a sequence longer than 4 before the grid starts repeating itself. 4 is the maximum number of unique states in a 3x3 wraparound CA grid, of the particular type we’re looking at today.

4x4 has a special place in my heart, and another special place in my wallet, since it started my career. I wanted to solve the 4x4 case, but I wasn’t getting anywhere with just pencil and paper. So I took an intro to programming class at my college, and solved it with my computer. When I cold emailed for my first programming job, I included my 4x4 CA result, which seems to have made a difference; when I came in for the interview they’d whiteboarded a 4x4 grid to check it out. So next time someone tells you 4x4 wraparound cellular automata is useless, you link ‘em right here!

Ahem. Let’s take it to the grid.

Since each cell has 8 neighbors, and there are 16 cells total, each cell is neighbors with exactly half the grid. So we start to see interesting patterns, rather than the totalitarianism of 3x3.

In fact, despite thinking about it for a long time with my fresh 17-year-old brain, I never found a better approach than brute force for 4x4 or up. That is, just take all the possible start configurations, filter them somehow to “unique” ones, then check every unique configuration against every rule and see which combinations last the longest.

To see what I mean by “unique” start configurations, consider the following two grids:

No matter what rule we give these grids, they are going to last the exact same amount of steps. In fact, we’ll see the exact same sequence, with each pattern shifted two cells to the left. Look closely and you’ll see:

This holds more generally; you can scoot an entire pattern up and down, left and right, or both, and the entire resulting sequence will be likewise shifted, and otherwise identical.

Or, consider these two configurations:

The one on the left is just a reflection of the one on the right; it will behave identically except for being reflected.

This one’s harder to spot, but the second pattern is just the first one rotated to the right. Same deal.

These two are inverted: all the living cells on the left are dead on the right, and vice versa. Inverted patterns are not the same for any given rule; however, if we’re only concerned with the longest chain of unique states (and we are), they are the same in a subtler way. Specifically, if we totally invert both the start configuration and the rule, we’d get the same pattern. For example, here’s the original pattern with the rule {3 on, 4 on}, and the inverted pattern with the rule {0 on, 1 on, 2 on, 3 on, 6 on, 7 on, 8 on}:

Meaning, if you’ll pardon a hand-wave, we can either divide the number of start configs or number of rules we check by two, since an inverted rule is just showing the exact same patterns with a switcheroo between “off” and “on.”

Putting all of our identities together, we can run an algorithm:

1. Take a start configuration we haven’t yet ruled out

2. Move it one to the left, then do all the nested steps; when done, repeat this step until it has been done three times total

   1. Move it one down, then do all nested steps; when done, repeat this step until it has been done three times total

      1. Rotate it 90 degrees to the right, then…

And so on.

By filtering on translations, reflections, and rotations, you can prune down the number of unique start configurations from 65,536 to a much more manageable 805. And by filtering on inversions, you can go from 512 rules to 256, so our total number of {rule, config} combinations to try is 206,080.

I crunched the numbers, way back in 2009, with my fresh computer skills. And determined that the answer is… 14.

Tada!

The faraway mathematical look in my eyes at the cafeteria table (along with the very long lashes around those eyes) helped me maintain the early attentions of my now wife, and my answer of “14” helped me jumpstart my career, so I rested on my laurels for a decade and a half. I didn’t quite give up, and would dutifully return to the problem once in a while, but my calculations suggested 5x5 would take a month or more of my computer running continuously. So my options were:

1. Get my computer to run 5x5 in the background, saving its progress as it went.

2. Come up with some much more sophisticated filtering regime so I could test fewer unique configurations.

3. Rent “supercomputer” time somehow/somewhere, which I had no idea how to do (I did literally think the word “supercomputer”), and was harder back then anyway.

I am ashamed to say that even though all these sounded cool and fun, I didn’t properly try until 2025. At that point, I noticed “hey, computers are stronger now and I can do the annoying technical comp-sci optimizations with AI while focusing on the fun Cellular Automata bit myself.”

Properly trying worked. With no further breakthroughs and liberal use of Cursor (I wasn’t yet on Claude Code) I verified the 4x4 case for the umpteenth time and got an answer for 5x5. Which is… 916.

Yep! This number did not surprise me at all, actually; the point of CA proper, when not confined to teeny tiny grids, is that simple rules generate huge complexity. So as the grids become less crowded, we should expect explosive growth.

I’ve written the post up to this point without ever attempting 6x6. I knew the implementation I used for 5x5 would be too slow, so I was satisfied just to gaze at the 5x5 gif and mutter “916” under my breath.

But it’s a new day. AI’s out there solving Millennium Prize Problems. So, swallowing my fickle human pride, holding tears back from my eyes, willing myself to be a pure and willing conduit for the avalanche of mechanical mathematical progress…

Computer! Please! What’s the answer to 6x6?

It’s 1,717. Not even twice as much as the 5x5 case. Weird!

I would have thought it would explode way faster, and be in the hundreds of thousands. But in fact, the ratio of the longest 6x6 chain to the longest 5x5 chain, is not even as large as the ratio between 4x4 and 3x3. You live and you learn.

Why is 6x6 so modest? I’m not sure, but one theory is that 6 is a highly divisible number, and 5 is prime. A fun result that Claude pointed out offhand while solving 6x6 is that if you tile four 3x3 grids to make a single 6x6 grid, the four 3x3 grids will act exactly like the 3x3 case, meaning you can only get to a maximum of 4 turns. I didn’t find this intuitive, at first. But it checks out.

Not many start configurations are tiled, so it in itself is not a big deal. But it’s a hint that prime grids may just be weirder than nice divisible ones. Or maybe not! At this point, I’m guessing.

While we’re here, I’ll remark that the solutions for 4x4 and 5x5 are close to unique, when you filter out the duplicates. 6x6 is actually unique: only a single start configuration against a single rule (again, excluding duplicates) reaches 1,717.

If you’ve gotten this far, perhaps you’d like to see the code. So before we go off into wild speculation, here it is. Lots of it is from my 2025 efforts, which first solved 5x5. You can find the code for 6x6, which was created since I started this post, under “fast.”

Not yet. Sampling 20,000 random start configs per rule in 7x7 turned up a longest sequence of 545,752 steps, so the answer has to be at least that high. As a rough guess, my CPU would take 270 years to find the answer, and my computer as a whole (with its GPU fully leveraged) would take 5 years straight. I could buy some fancier GPU time online to run tests in parallel, but it would probably cost somewhere around $10,000. My son is due to be born in a few days, and my daughter turns 2 a few days after that, so I probably shouldn’t spend $10,000 chasing this white whale.

There are probably fancy engineering tricks that could get 7x7 in reach, perhaps getting the cost down to just a few hundred dollars, or a few months of running in the background on my computer. But it might take substantial work.

Cellular automata is special because simple rules can create extremely complex emergent behaviors. My zany fiddling with tiny grids is a way to bottle that lightning, and see how chaotic you can still get under near-total constraint. But as the constraint relaxes and grids get larger, irreducible complexity creeps in. You can come up with clever algorithms and sample intelligently, but at the end of the day the only way to know the maximum is to check everything.

I might solve 7x7 someday, if nobody reading this is nerdsniped and gets to it first. But I’m not doing it today.

Forget about it. Sampling 2,000 start configs per rule turned up a sequence of 5,064,397 steps. Even with millions of dollars of compute, all I could do is make an educated guess. And as we approach 9x9, 10x10, 11x11, we creep towards territory where even if humanity dedicated all of its resources into solving the problem, we might fail. By 16x16 it’s probably physically impossible, requiring a computer the size of many galaxies. And so on.

Still, this whole project is about small grids. At the moment, we can draw the line at 6x6, and call our sequence complete. 4, 14, 916, 1,717. Those are the wraparound CA maximum termination numbers, for the smallest square grids. Now we know.

Beyond lies only sampling and madness. Unless you, dear reader, see a better way.