8
$\begingroup$

First of all, i'll confess i'm no math geek. I'm from Stackoverflow, but this question seemed more apt here, so i decided to ask you guys :)

Now, i know noone has discovered (or ever will) a Polynomial that generates Prime Numbers. But i've read about Curve Fitting (or Polynomial Fitting) so i was wondering if there was a way, we could have a simple n-degree Polynomial that could generate the first 1000 (or X) primes accurately.

I don't need it to generate all the primes, maybe just upto 1 million, since we already have the data, can we deduce that polynomial?

How big will be the polynomial for it to be accurate? Could you give an example for the first 100 primes? Am i just plain naive?

Thanks in Advance. :)

  • 0
    See also $t$his: http://mathworld.wolfram.com/MillsConstant.html2014-05-03

2 Answers 2

11

While Robin was commenting, I cooked up a Mathematica one-liner which gives you the Lagrange interpolation polynomial for the first n primes:

f[n_] := Sum[Prime[k] Product[x-m,{m,Join[Range[1,k-1], Range[k+1,n]]}] / Product[k-m,{m,Join[Range[1,k-1], Range[k+1,n]]}] ,{k,1,n}] // Expand 

And I don't think anyone would call the results "simple". For n=100 it's too big to paste here, but n=15 gives

4748 - (1752758563*x)/120120 + (71043957851*x^2)/3783780 - (4320411427*x^3)/316800 + (378496362427*x^4)/59875200 - (7239131749*x^5)/3628800 + (11528263*x^6)/25920 - (2075348983*x^7)/29030400 + (5090997277*x^8)/609638400 - (977071*x^9)/1382400 + (743507*x^10)/17418240 - (568871*x^11)/319334400 + (2207*x^12)/45619200 - (3151*x^13)/4151347200 + (89*x^14)/17435658240

  • 0
    @J. M.: Nice! I didn't know there was a builtin function for that. Of course, wrapping your expression in Expand[ ... ] gives the same result as mine, but in a much cleaner way.2010-10-17
9

From Mathworld

However, there exists a polynomial in 10 variables with integer coefficients such that the set of primes equals the set of positive values of this polynomial obtained as the variables run through all nonnegative integers, although it is really a set of Diophantine equations in disguise (Ribenboim 1991). Jones, Sato, Wada, and Wiens have also found a polynomial of degree 25 in 26 variables whose positive values are exactly the prime numbers (Flannery and Flannery 2000, p. 51).

Unfortunately, the primes do not come out in order, so this will not help for what you want. But it is interesting.