At the opposite end of the spectrum from industrial strength methods
such as Miller-Rabin are generators which produce primes with minimal
(and apparently insufficient) resources.
Here are two of my favorites.
Rowlands' generator
This is a simple recurrence relation, starting with 7, whose first
differences are either 1 or prime.
f=:,{: + >:@# +. {:
d=:2 -~ /\ ]
1 -.~ d f^:1000 ] 7
5 3 11 3 23 3 47 3 5 3 101 3 7 11 3 13 233 3 467 3 5 3 941 3 7
Conway's Fourteen Fruitful Fractions
This is more mysterious. We take a list of fourteen magic fractions.
At each step we have an integer, starting with 2. We multiply the
integer by each of the fractions from left to right until we get
another integer. This is the next iterate. When an iterate is a
power of 2, the exponent is the next prime.
num=:17 78 19 23 29 77 95 77 1 11 13 15 15 55x
den=:91 85 51 38 33 29 23 19 17 13 11 14 2 1x
fff=:num%den NB. The fractions
h=:{.@:(#~ (=<.))@:(fff&*)
k=:(#~ (=<.))@:(2&^.)
k h^:(i.1e4) 2
1 2 3 5 7 11 13 17
Does anyone have any similar examples?
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
