I came up with a cellular automaton for factoring numbers. Fairly ironheaded and I’m sure not novel but a fun exercise for me. Here’s the Golly rules file. Yeah, there’s 13 states. I did say ironheaded.
In the initial state there are two cells on, one in state 1 (blue) at and one in state 2 (dark red) at (with ). Here’s :The CA starts building some infrastructure: a top axis () in dark red, a vertical axis () in blue, a bottom axis () in light green, and a main diagonal () in dark green. The bottom axis is where results will be shown: after generations, cell will be red if and only if is a factor of (for ).But in that picture the top and left axes and the main diagonal are only half finished, and there’s other stuff going on. What’s that? It’s already testing numbers to see if they’re factors. The infrastructure’s not complete but there’s enough there to get started.
Here the top and left axes and the main diagonal are completed, and the bottom axis is under way. On the right is a grey glider heading south, which will tell the bottom axis where to stop. And here the bottom axis is done, in time for a blue south-going glider to mark 6 as a factor. 1 is already marked as a factor: the regular CA mechanism won’t work for , but it’s kind of safe to assume is a factor of , so it’s marked as such immediately. So is . Here the process is nearly finished. Four factors are marked:After 33 generations, action stops, with factors at 1, 2, 3, 4, 6, and 12 marked.It works as follows: For each from down to , at the top axis a slow south-going (S) glider, with speed where means one cell per generation, and a SW-going glider with speed are dropped. When the SW glider hits the vertical axis it bounces off as an E glider (again speed ). After generations the two gliders will collide, unless they hit the main diagonal first, in which case they’re deleted. If they collide before hitting the main diagonal the E glider bounces back SW, hits the vertical axis, and bounces back E for another potential collision after generations. This continues, with the SW/E glider bouncing off the S glider and hitting the vertical axis at intervals of cells, until they collide with the main diagonal and are destroyed… or they collide with each other on the main diagonal. If that happens then obviously a bounce to the SW would send that glider to the origin, and that means (the length of the vertical axis) is evenly divisible by . But instead of bouncing SW in that case, a new fast (speed ) S glider is dropped to the bottom axis, where it marks cell as a factor.
What’s tricky here is that this whole process is launched for one generation after it’s started for ! So a whole bunch of potential factors are being tested at any given time. It’s not obvious this can be made to work, especially since various SW and S gliders are launched cheek by jowl, and the slow S gliders are two cells wide. But it does work.
Here’s a couple videos: Testing :
giving results 1, 2, 3, 4, 5, 10, 15, 20, 30, and 60, and testing :
, so there’s not much action on the bottom axis until just moments before the end.
A little more searching turned up this paper by I. Korec called “Real time generation of primes by a one dimensional cellular automaton with 9 states”, which is pretty much what it says on the box. He shows a 1D CA where the cell at the origin is in a particular state (“1”) in generation if and only if is prime.
The rule list is rather lengthy and he doesn’t explicitly give it (nor did I find it elsewhere). Instead he shows the history for the first 99 generations and says you can infer most of the rules from that; the rules that don’t enter in until after that point he lists. So I cut and pasted his history and wrote a little Python script to extract the rules list, from which I created a Golly .rules file. I guess it would’ve been possible to make the states look like Korec’s symbols but I didn’t bother; I just used different colors. Korec’s states “.”, “/”, “0”, “1”, “L”, “R”, “r”, “V”, and “v” are states 0 through 8, respectively.
The initial state for the CA is just a “0” (state #2 in this rules file) in one cell. The CA will be built toward the right and the first cell will be “0” in non prime generations, “1” (state #3) otherwise. It looks like this at generation 30:At generations 3, 11, 113, 307, 311, and 1103 the leftmost cell is green, so I’m thinking it works.
Today, Nov 3 (11/3 or 11/03 or 3/11), is the 307th day of 2015. And 3, 11, 113, 1103, 311, and 307 are all prime. Ignore Amazon, THIS is PrimeDay. (But next year it’s March 11, because 308 is not prime, but 71 is.)
So since I’ve been playing with cellular automata lately, here’s some prime CA material.
Dean Hickerson came up with primer, a Life pattern that generates prime numbers, back in 1991. Nathaniel Johnston wrote about it in a 2009 blog post, mentioning twin and Fermat prime variants devised by Hickerson and Jason Summers, and then going on to present patterns that generate Mersenne primes, prime quadruplets, cousin primes, and sexy primes.
Primer looks like this once it gets going:
Which looks pretty complicated but it isn’t really so much. What you have are some puffers that lay down three rows of period 30 glider guns, one vertical and two horizontal. In the horizontal rows each gun in the top row kills the glider produced by the corresponding gun in the bottom row, unless there’s a gap in the first row’s output in which case the bottom row gun makes a glider: what you have there is an inverter, where a gap in the top row’s output becomes a glider in the bottom row’s, and vice versa.
Coming in to each of the top row guns is a glider which gets kicked back, killing the top row’s glider in the process and creating a gap. That kicked back glider travels up to the vertical row where it gets kicked back again to interact with the top row gun again. Obviously this circuit takes a shorter amount of time for the guns at the left (kicking back to the guns on the bottom of the vertical row) than for the guns at the right (kicking back to guns higher up). In fact what happens is there is a gap every 12 gliders coming out of the first top row gun, every 20 gliders for the second, every 28 gliders for the third… every for the th. After inversion, there’s a glider coming out of the th bottom row gun every generations. There’s also a puffer seen toward the right that starts up the kickback reactions by sending a glider toward the next vertical gun when it’s ready.
Then there’s a lightweight spaceship gun sending spaceships west every 120 generations. But if a glider comes off the bottom row it kills a spaceship. So the first gun would kill every third spaceship (if nothing killed any others), the second would kill every fifth spaceship, the third would kill every seventh, and so on. Which is just the Sieve of Eratosthenes. What’s left is a spaceship passing a certain point at generation if and only if is prime.
Hickerson’s primer and three improvements by Jason Summers are included in the patterns folder that comes with Golly, as are the Fermat and twin prime generators. The Fermat generator, also by Summers, has four tubs which are destroyed at about generations 50; 1,490; 30,290; and 7,863,890 (corresponding to the second through fifth Fermat primes 5, 17, 257, and 65537). If a sixth Fermat prime is generated it destroys a pond and shuts the pattern down. Since the sixth Fermat prime is known, as of 2014, to be at least , the pond will not be destroyed in fewer than about generations, which will take a while depending on your computer.
Also included in the Golly patterns is a CA by Adam P. Goucher (under Calcymon-primer in the Other Rules folder). It’s a 10-state CA with a Moore neighborhood which is designed to allow a primer that’s a little simpler than Hickerson’s Life primer. Goucher’s primer in its initial state looks like this:Two cells! Here it is after about 70 generations having produced 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31:
It works kind of similarly to Hickerson’s primer; here the kicked back single cell “gliders” (red going up, green going down) get re-kicked with a delay to increase the spacing between, so on the first trip they knock out every third output spaceship (being produced on the diagonal blue line), every fifth one on the second trip, every seventh one on the third, and so on. Much less messy and faster than the Life version, though I don’t know if it can be adapted for Fermat primes, and if so it’ll still take longer than you might want to wait to find the sixth one.
Anyway, happy Prime Day!
So, A054247. There’s a formula:
if is even and
if is odd.
Can we derive that?
Let’s look at the simplest nontrivial case, . There are possible soups. But some of these are equivalent to others under rotation or reflection… and some aren’t.
That is, define the following transformations:
- r0 = I, the identity transformation
- r1, 90° rotation clockwise
- r2, 180° rotation
- r3, 270° rotation clockwise (or 90° counterclockwise)
- s0, reflection in a vertical axis
- s1, 90° rotation clockwise then reflection in a vertical axis (equivalent to reflection in a NW–SE diagonal axis)
- s2, 180° rotation then reflection in a vertical axis (equivalent to reflection in a horizontal axis)
- s3, 270° rotation clockwise (or 90° counterclockwise) then reflection in a vertical axis (equivalent to reflection in a NE–SW diagonal axis)
Two configurations are equivalent if applying any of these transformations to one results in the other.
A configuration can have various symmetries, wherein applying one or more of these transformations to it results in the same configuration. For example, any transformation applied to the all cells dead pattern gives the same pattern back. That means that pattern isn’t equivalent to any other pattern. Likewise the all cells live pattern.
The following symmetries are possible:
- r1r2r3s0s1s2s3: invariant under any of these transformations. (Everything is invariant under r0 = I so it’s not mentioned.) 2 by 2 example:A pattern with this symmetry is equivalent to no other patterns.
- r1r2r3: Invariant under any rotation but not under reflection. No 2 by 2 or 3 by 3 pattern has this symmetry but here’s a 4 by 4 that does:
A pattern with this symmetry is equivalent to one other pattern (its mirror image).
- r2s0s2: Invariant under 180° rotation or reflection in a vertical or horizontal axis. No 2 by 2 instances. Here is a 3 by 3:A pattern with this symmetry is equivalent to one other pattern (its 90° rotation).
- r2s1s3: Invariant under 180° rotation or reflection in a diagonal axis. 2 by 2 example:A pattern with this symmetry is equivalent to one other pattern (its reflection in a vertical or horizontal axis, or its 90° rotation — both are the same).
- r2: Invariant under 180° rotation. 3 by 3 example (there are no 2 by 2):A pattern with this symmetry is equivalent to three other patterns (its reflection in a vertical or horizontal axis, its 90° rotation, and its reflected 90° rotation).
- s0: Invariant under reflection in a vertical axis. 2 by 2 example:A pattern with this symmetry is equivalent to three other patterns (its reflection in a horizontal axis, or its 180° rotation — both are the same — and its 90° or 270° rotations).
- s1: Invariant under reflection in a NW–SE diagonal axis. 2 by 2 example:A pattern with this symmetry is equivalent to three other patterns (its 90°, 180°, or 270° rotations).
- s2: Invariant under reflection in a horizontal axis. Equivalent to three other patterns.
- s3: Invariant under reflection is a NE–SW diagonal axis. Equivalent to three other patterns.
- I: Not invariant under any transformation. 3 by 3 example (there are no 2 by 2): Equivalent to seven other patterns (its transformation under r1, r2, r3, s0, s1, s2, or s3).
That there are no other symmetries may not be entirely obvious. But do some thinking: For instance, any pattern invariant under r1 must be invariant under r2 and r3, because the latter are just r1 done twice or three times. Likewise any pattern invariant under r1 and s0 must be invariant under s1, s2, and s3, because these are just r1 once, twice, or three times followed by s0. Similarly r2 and s0 imply s2, and r2 and s1 imply s3.
Think about a large square pattern that is invariant under r1r2r3s0s1s2s3. Under those transformations the corners map onto the other corners; the cells left of the center line on the top row map into the cells on the right of the center line on the top row as well as all the cells in the bottom row and left and right edges; and so on. Specify only the cells on or above the main diagonal in the upper left quadrant of the pattern and you’ve specified the whole thing. In an pattern where is even, the number of cells you need to specify is where is the th triangular number. Where is odd, the number of cells is . That means the number of such patterns is or . None is equivalent to any other pattern, so all are added into the number of unique patterns after reflections and rotations.
For a pattern invariant under r1r2r3, if is even you need to specify all the cells in one quadrant; there are such cells. For odd, r1 takes the bottom row of the top left quadrant into the right side of the same quadrant, so in that row all but the center cell of the pattern are constrained: you specify all the cells of one quadrant, except one row, except one cell: cells. So there are then or possibilities — but they include all the r1r2r3s0s1s2s3 patterns too. The number of patterns invariant under r1r2r3 but not r1r2r3s0s1s2s3 is or . Each is equivalent to one other pattern, so the number added into the total after reflections and rotations is half of this.
Next is r2s0s2. This maps the left side of the top row to the right side of the top row and both sides of the bottom row, and so on. Here you have to specify all the cells in one quadrant if is even or odd. This means there are or possibilities, but again you have to subtract off the r1r2r3s0s1s2s3 patterns, leaving or . Again, divide by 2 for the contribution to the total after reflections and rotations.
And so on. For each of the symmetries you can figure out how many cells you have to specify, which tells you how many patterns there are; then you have to subtract off the number that have already been counted under higher symmetries, then divide by the number of equivalent patterns for that symmetry. Rather tedious to do all of it algebraically for general , so I won’t, but you have the ammunition if you want to. I have found the figures for 2 by 2 through 4 by 4 by hand and with a brute force Python script, and they agree:
You can see how rapidly the number of asymmetric (I) patterns comes to dominate the total, so that the number of unique patterns after reflection and rotation approaches .
Edit: What the heck, I made a Google spreadsheet with the figures for square soups up to 16 by 16.
Hm, been just two days under a year since my last post here. Life goes on. So does Life.
This is about http://catagolue.appspot.com/home. No, that’s not a typo. It’s catagolue, i.e. cataGOLue, i.e. cata-GameOfLife-ue. Adam P. Goucher set this up as a repository for crowdsourced results of running Life with random 16 x 16 “soups” as initial configurations, using one of two “apgsearch” software tools: an earlier one in Python and Version 2.x in C++. The Python version is more flexible — it can search alternate rules, not just B3S23, and one can specify initial soups with some level of symmetry. The C++ version is B3S23, asymmetric soups only, but runs about seven times faster.
Is there any real point to doing this? I don’t know, but I find it amusing.
To use the C++ version you download it, compile it (x86-64 machines only; Linux, Mac, or Windows), and run it with a command line like
./apgnano -n 20000000 -k mykey -p 4
Here you’re telling the program to generate and follow 20000000 soups per “haul”. On my old iMac that takes about two hours. “mykey” is a key to allow it to upload your results non-anonymously; they’ll be uploaded anonymously if you omit it. “-p 4” tells it your machine has 4 cores it should use.
My results are uploaded using the ID “@doctroid“. When a previously un-found object is discovered it gets tweeted by @conwaylife, so using “@doctroid” for my ID means the tweet carries a link to my Twitter account. My results also get posted at my catagolue page.
So far all the still lifes of size 13 and under, and almost all the size 14 ones, have turned up “naturally” from 960 393 995 873 random soups. So have 744 period-2, 120 period-3 and 12 period-4 oscillators plus a number with periods above 4. The project’s also found a bunch of spaceships — but all of them are gliders, light-, middle-, or heavy-weight spaceships, or compounds thereof. There’s a €50 bounty offered for the first “naturally occurring” spaceship that isn’t! A bit surprisingly to me, four puffer trains have been found too. In fact, two of them are among the 100 most common objects.
960 393 995 873 soups; nearly a trillion! How many are left?
I’m surprised I can’t find more on that question online. Obviously there are only two soups: * and -. There are soups but only six are distinct under rotation and reflection:
-- *- ** *- ** ** -- -- -- -* *- **
gets to be harder to count. There are possibilities but many are equivalent under rotation and reflection. The relevant sequence in OEIS is A054247 Number of n X n binary matrices under action of dihedral group of the square D_4. After accounting for rotations and reflections there are 102 distinct soups. And 8548 , and… well, let’s cut to the chase. OEIS doesn’t show the value for but nearly all large soups have no symmetry so it’s a good approximation to say for size there are about soups when is large. For that’s about . I don’t think the catagolue will be completed any time soon.
(This is somewhat old news and I should have mentioned it here earlier. Well, better late than never.)
is a spaceship!
I was 15 in 1970 when Martin Gardner first wrote about Life in his Mathematical Games column. I was reading Scientific American regularly by then. I was fascinated by Life. I remember working out patterns using small poker chips on a go board — I took several days to work through the 30 generations of Gosper’s Glider Gun. I got a subscription to Lifeline. I read about people who had access to computers they could use to explore Life patterns and thought that would be very cool. (Mark sense card BASIC on our high school’s PDP-9 wasn’t quite it.)
Spaceships were especially cool, and of course everyone knew there were only four of them: the Glider and the Light-, Middle-, and Heavyweight Spaceships. Well, and Overweight Spaceships stabilized by accompanying flotillas. Or the above orthogonal spaceships with accompanying tagalongs. Or puffer trains cleaned up with accompanying orthogonal spaceships to leave no exhaust, thereby becoming spaceships. None of which seemed really to be a spaceship to me, or at least a fundamentally different spaceship. In particular they all had period 4 and speed c/2.
About 20 years later, I was staggered to learn entirely new Life spaceships had been discovered. As David I. Bell writes (gzipped Postscript file), in 1989 Dean Hickerson wrote a Life search program for his Apple IIe and discovered two period 2, speed c/2 spaceships, and soon developed an infinite family of such ships based on combinations of various building blocks. They’re all much larger than the Glider and the original orthogonal Spaceships, with the smallest ones having minimum population I think about 64 live cells. They can be built up into large, long and narrow, very impressive structures, but they certainly aren’t simple.
And from there the floodgates opened. Huge numbers of distinct spaceships now are known. You can read about some of them here. There are diagonal ships with speeds c/4, c/5, c/6, c/7, and c/12, orthogonal ships with speeds c/2, c/3, c/4, 2c/5, c/5, c/6, 2c/7, and 17c/45, and enormous slope 2 and slope 5 ships with the boggling speeds of 2048c/17783745 and 2560c/16849793, respectively; but until this year no orthogonal c/7 ships were known.
On Feb. 11 on the conwaylife.com forums, Hartmut Holzwart wrote:
Now with several new versions of search programs out and PCs still getting more powerful, it might be time to revisit [c/7 orthogonal spaceships.]
Are there any serious search results out there? Promising intermediate results? Ideas?
Six days later Josh Ball responded:
I found a c/7 spaceship!!! And it’s small, min pop 20 cells.
Several other forum readers assumed he was joking; he wasn’t. His spaceship is the one shown at the top of this post, and it’s real. Due to its slow speed and the fact that it pushes a Loaf along, this new spaceship is called a Loafer. Not only is it the first known orthogonal c/7 spaceship, I believe it also is the smallest known spaceship other than the original four. Such a tiny spaceship and it avoided detection for over 40 years!
Well, but how tiny is it? It fits into a 9×9 square. So do 281-1 = 2,417,851,639,229,258,349,412,351 other patterns. (Remember the Wheat and Chessboard problem? This is a 9×9 chessboard, which is a lot worse.) If you did a brute force search and analyzed a thousand patterns a second, it’d take 77 trillion years to look at all of them. Obviously, then, Ball did not just do a brute force search. In fact he said he found half of the Loafer a while ago — presumably he noticed it acted promisingly, nearly replicating itself with a displacement after 7 generations — but he couldn’t at that time make a complete spaceship out of it; he went back to it after Holzwart’s query, and found the other half. Brains beat brute force, in this case by factors of 1013 or so. It’s very hard — really, it’s impossible — to grasp the scale of the disconnect between how small the Loafer looks and how large the search space is. Even after writing that enormous number out, and converting to years, it still feels surprising that no one had stumbled across this ship a long time ago.
Just goes to show Life probably still has lots of big surprises waiting to be found.