In the prime of life (part 2)

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 t if and only if t 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:Screen Shot 2015-11-04 at 8.13.42 PMAt generations 3, 11, 113, 307, 311, and 1103 the leftmost cell is green, so I’m thinking it works.



Leave a Reply

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

You are commenting using your 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