Finding Primes Using Cellular Automata

It just occurred to me that distribution of primes looks VERY much like the output of a cellular automaton rule. This makes me wonder whether it might be possible to use a cellular automaton to generate prime numbers. If we can find the rule that generates the prime numbers, perhaps this rule has other important properties. Just a hunch. In any event, it would help to explain the distribution of primes. Below I discuss some approaches to doing exhaustive searches for CA rules that generate the primes.

Here’s how such a rule might work: Simply adopt the convention that non-primes are cells with state 0 and primes are cells with state 1. Make a 1-dimensional cellular automaton. Next select a given COLUMN (not row) to represent the “output” of our computation — The goal is to come up with a rule and initial conditions that causes the bits in our chosen row to turn on and off such that the output bit at time n indicates whether integer n is prime or not. Interesting huh?

It also occurs to me that we could simply search for this experimentally by analyzing all rows and columns in the output of all 2-state 1D CA rules on all initial conditions (of a given number of cells) to see if any of them match the prime number distribution. We can start our experiment in a simple way — choose a small number of cells initially — say 10 — enumerated 0..9. Between 0 and 9 there are the following primes: 2, 3, 5, 7. So we want to begin our search by looking for CA’s that contain patterns that match 00110101 (cell 0=not prime, cell 1 = not prime, cell 2 = prime, etc.). If we find such a pattern, then we simply have to look at the next 2 cells to see if it generating the prime numbers (if the next two cells are 01, then so far, so good and continue looking at adjacent cells; if the pattern breaks then stop testing this segment and look somewhere else).

In thinking about this a little further I’ve realized that we could use a genetic algorithm to search for the rule and initial conditions. Simply represent the first n integers as a line of cells with states 0 or 1, corresponding to whether integer n is not-prime or prime. We can view this line of cells as horizontal (the state of one step of time in the system), or vertical (the state of a single cell across steps of time). Now we just have to evolve CA rules that generate this sequence of cells. This might be the best way to find our prime generator rule.

This is an easy experiment to do for anyone who is fluent in Mathematica and has some time on their hands. If you happen to do it, I would love to hear the results!