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?