It's an old problem to find a formula for primes. With so little success, we lower our sights, and look for formulas that produce primes for a while, or that produce more primes than expected. For polynomials, it looks like a formula can raise the percentage of primes by a constant factor. (Trivial example: 30N+1 has 3.75 times as many primes as N.) Challenge: Find a formula with a better "score" -- One whose values are more likely than average to be prime, with the improvement more than a constant factor. N!+1 might work, but any improvement over 1/logN is microscopic. The baseline assumes a prime likelihood of 1/logN. I'm not sure how to score formulas like 1+2^2^N, which we would accept as a perfectly valid prime formula if it worked, but whose total sum 1/logN is bounded. If we limit ourselves to formulas with sum 1/logN unbounded, the universe of potential formulas is much smaller. But if we don't, the set of numbers grows too fast to test very many. More sophisticated challenge: Find a formula whose prime likelihood is something different from Constant * 1/logN. Or a formula that generates numbers *less* likely to be prime, excluding trivialities like X^2 + X + 4. Or a formula that has anything other than the usual expected distribution for the number of distinct prime factors. (Again, excluding trivialities like N^2 or N^2-1.) Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Ed Pegg Jr Sent: Mon 6/26/2006 8:09 AM To: math-fun Subject: [math-fun] Prime Generating Polynomials I'm not sure if it's been mentioned here. The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating Polynomials. For example, one polynomial that generates 49 primes is x^4 - 97*x^3 + 3294*x^2 - 45458*x + 213589, first found by Mark Beyleveld and later by 5 other participants. Even better polynomials were found. More results: CUBIC: -66 x^3 + 3845 x^2 - 60897 x + 251831. Prime for x=0 to 45. Ivan Kazmenko and Vadim Trofimov. 42 x^3 + 270 x^2 - 26436 x + 250703. Prime for x=0 to 39. Jaroslaw Wroblewski and Jean-Charles Meyrignac. QUARTIC: x^4 - 97x^3 + 3294x^2 - 45458x + 213589. Prime for x=0 to 49. Mark Beyleveld. QUINTIC: (x^5 - 133 x^4 + 6729 x^3 - 158379 x^2 + 1720294 x - 6823316)/4. x=0 to 56. Shyam Sunder Gupta. x^5 - 99x^4 + 3588x^3 - 56822x^2 + 348272x - 286397. x=0 to 46. Jaroslaw Wroblewski & Jean-Charles Meyrignac. SEXTIC: (x^6 - 126 x^5 + 6217 x^4 - 153066 x^3 + 1987786 x^2 - 13055316 x + 34747236)/36. Prime for x=0 to 54. Jaroslaw Wroblewski & Jean-Charles Meyrignac. Full details and findings will eventually be published at At http://www.mathpuzzle.com/ I have about 40 other math stories... it's been a busy month. Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun