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!

Advertisements

One thought on “In the prime of life

  1. I guess “factorization” may be a misleading term to use here, since usually that tends to imply prime factors. This CA of course finds all divisors of a number, prime or composite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s