Are there simple procedures or fractals that "compute" prime numbers?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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