In the prime of life

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:

Screen Shot 2015-11-03 at 10.28.37 AMWhich 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 4(2n+1) for the nth. After inversion, there’s a glider coming out of the nth bottom row gun every 30\times 4(2n+1) 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 120n if and only if n 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 2^{(2^{33})}+1, the pond will not be destroyed in fewer than about 10^{2,560,000,000} 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:Screen Shot 2015-11-03 at 11.13.31 AMTwo cells! Here it is after about 70 generations having produced 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31:Screen Shot 2015-11-03 at 11.12.42 AM

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!

Life goes on

Hm, been just two days under a year since my last post here. Life goes on. So does Life.

This is about 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.

There you can see I’ve “discovered” two objects at this writing; one’s a period 3 oscillator, a cuphook variant:chvand the other’s a period 2 oscillator, a test tube baby variant:ttbv

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 1\times 1 soups: * and -. There are 2^4=16 2 \times 2 soups but only six are distinct under rotation and reflection:

--  *-  **  *-  **  **
--  --  --  -*  *-  **

3\times 3 gets to be harder to count. There are 2^9=512 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 3\times 3 soups. And 8548 4\times 4, and… well, let’s cut to the chase. OEIS doesn’t show the value for n=16 but nearly all large soups have no symmetry so it’s a good approximation to say for n\times n size there are about 2^{n^2}/8=2^{n^2-3} soups when n is large. For n=16 that’s about 1.4474011\times 10^{76}. I don’t think the catagolue will be completed any time soon.


Small and slow

(This is somewhat old news and I should have mentioned it here earlier. Well, better late than never.)


Loaferis 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.

Soon after, Hickerson started looking for period 3 ships, and he found building blocks for those too. The smallest such ship is only 25 live cells in each generation:p3ship

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 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.