Are there simple procedures or fractals that “compute” prime numbers?

Prime numbers are often computed with very procedural, "artificial-looking" algorithms, such as consecutively checking divisors up to the square root, risking numbers in tables (sieves), and so on. Fibonacci numbers, on the other hands, can be "computed" from a very simple rewrite system:

axiom  : A
rules  : (A → AB), (B → A)


If you repeatedly apply the rules to the axiom, you get this sequence of strings:

n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB


And, if you count the length of each word, you get the sequence of Fibonacci numbers!

Are there are similarly simple ways to generate prime numbers?

• @mvw per the rules, from 1 (AB) to 2 (ABA), the A is replaced by AB, the B is replaced by A... AB + A == ABA. – TreeHaunter Apr 22 '17 at 6:36
• The derivation $A\to AB\to ABB\to ABBB$ has length $4$, which is not element of the usual Fibonacci sequence. – mvw Apr 22 '17 at 6:38
• This is in fact essentially the original way the Fibonacci numbers were described; B being a pair of rabbits just born, and A being a pair of rabbits mature enough to begin reproducing. In a month, a B changes into an A, while an A remains the same but additionally produces a new B. – Sridhar Ramesh Apr 22 '17 at 12:26
• Have you analysed the difference between a consecutive terms in the progression? – usiro Apr 26 '17 at 20:34

Well, if by "fractal" you accept a more "visual" concept, there are examples of visual sieves of prime numbers, like the one devised by Yuri Matiyasevich and Boris Stechkin, this is an excerpt of their own explanation (all credits to them, original source here, just written and shown here for the purpose of explaining the sieve):

The straight line connecting points $(i^2,-i)$ and $(j^2,j)$ (lying on the parabola $x=y^2$) crosses the x-axis at the point with of abscissa $ij$. Thus, if we connect all such points for $i,j=2,3,...,$ then all composite numbers will be "crossed out" from the positive part of the axis of abscissas.

• @EthanBolker thanks for the markdown, on weekends I write from a tablet and formatting Mathjax is a nightmare. – iadvd Apr 22 '17 at 13:21
• That is so interesting! Definitely the kind of answer I was looking for. I want more! – TreeHaunter Apr 22 '17 at 14:00
• @TreeHaunter there is a primality test based on Fibonacci numbers, I think can be seen at the Wikipedia, so your example of Fibonacci could be indeed used to obtain the prime numbers with some extra manipulation. There is a "but" about that primality test: unfortunately, there exist Fibonacci pseudoprimes. But this idea is very close to your initial point about a rewrite system. – iadvd Apr 22 '17 at 14:33

According to wikipedia, the set of primes (represented as numerals in the usual fashion) can't be presented by a context-free grammar.

However, given the criterion on wikipedia, I'm nearly certain there is a context-sensitive grammar that gives primes.

In fact, I think I even have an idea of how to make a context-sensitive grammar whose production rules implement a sieve, although it's complicated enough that I'm not inclined to try to write it down.

• Nice to know it is not possible with a context-free grammar, but couldn't we be more creative, explore other structures? Perhaps some cellular automata, rewrite rules on graphs not strings, etc.? – TreeHaunter Apr 22 '17 at 6:34

A FRACTRAN program that generates the primes can be seen as such a system.

• Very nice example. – mvw Apr 22 '17 at 15:03

The answer depends on what you consider simple.

Considering Hurkyl's link, which locates the problem of listing all prime numbers in the upper half of the Chomsky hierarchy, I would not consider the needed computational models as simple.