Rutgers Graduate Student Finds New Prime-Generating Formula

The summer school where this was conjectured was <a href="http://www.wolframscience.com/summerschool/2003/participants/" rel="nofollow">http://www.wolframscience.com/summerschool/2003/participants...</a><p>As one of the "live experiments" Stephen Wolfram decided to try to find the minimal recursive functions involving arithmetic type operations that produce complex behavior. The article glosses over this, but no one set out to find a function that produced only primes; it just so happened that when enumerating these minimal functions this one was discovered to have a peculiar regularity.<p>By the way, if you ever discover an efficient way to generate primes, you have a shot at claiming a 100k prize (<a href="http://www.eff.org/awards/coop" rel="nofollow">http://www.eff.org/awards/coop</a>)

Off-topic, but it's interesting how he's reimplemented a substantial fraction of Haskell's Prelude (base library) in Mathematica, probably without knowing it: <a href="http://www.math.rutgers.edu/~erowland/programs/ListTricks.m" rel="nofollow">http://www.math.rutgers.edu/~erowland/programs/ListTricks.m</a>.

The formula (or rather the algorithm) is interesting, but rather impractical. First million of iterations generate only 36 primes, and these are not even sequential:<p><pre><code> 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 47, 53, 101, 127, 163, 199, 233, 421, 443, 467, 577, 941, 1889, 3779, 7559, 15131, 30323, 60647, 121403, 242807, 486041, 972533, 1945649, 3891467, 7783541</code></pre>

the caveat being that the complexity of computing the formula is at best on the order of preexisting techniques, so nifty deep math, but nothing new from a computational point of view (barring more insight happening)

Man, I went to Rutgers, but it sounds like I picked the wrong major. One of my CS TA's literally did not know what the head and tail of a list are (an American, by the by). And to think, math was just across the hall..

I have also developed a Formula that generates only 1 and primes:<p><pre><code> a(n) = 1</code></pre>

Anyone know whether it's been proven that the formula will generate an infinite number of primes? Or might it start looping back on itself eventually?