1
$\begingroup$

Here's a simple polynomial that generates quite a few primes (not necessarily consecutive).

$p(n) = n^2 + 23n + 23$ with $n=0,1,2... $

What can such polynomials tell us about primes? Thanks.

Edit 1.

I am posting the general method to generate an infinite number of these prime generating polynomials because I think it may be useful to their study.
I will provide the example of the polynomial starting with the integer 1 and using square integers, namely the main diagonal of the classical multiplication table.

p(n) = (1+n)(1+n) + 2 + n

We see here that for n=0, p(0) = 3. Adding 2 is done to precisely achieve that result, that is to get a prime. The rest will take care of itself.

p(n) = n^2 + 3n + 3

Now there is nothing special about the starting point 1, the first integer. One can build a quadratic prime generating polynomial for every integer. As an example, here's the polynomial starting with the integer 2.

p(n) = (1+n)(2+n) + 1 + 2n = n^2 + 5n +3

The only reason the term 2n was added instead of n, like above, is because we need p(n) to be odd for every single value of n and the starting integer is even.

The first polynomial I posted had in fact a starting point of 21, not 23.

p(n) = (21+n)(1+n) + 2 + n = n^2 + 23n + 23

The choice of adding 2 is dictated by the fact that 23 is the next prime if we are starting at 21. But there is no rule that says we can't use 8 and get 29 as the next prime. It's just that there is no rational motivation to skip a prime.

$\endgroup$
6
  • $\begingroup$ From n=0 to n=100, the above polynomial generates 74 primes. It would be interesting to see if the trend continues for larger values of n. $\endgroup$
    – user25406
    Apr 4, 2015 at 19:06
  • 1
    $\begingroup$ I'm not sure if it generates infinitely many primes. If Bunyakovsky's conjecture is true, that means it does. It generates $1275$ primes between $0$ and $3200$, so the density seems to get smaller as $n$ gets bigger. I'm not sure, but I think the density of primes gets closer to $0$ as $n$ goes to $\infty$. $\endgroup$
    – Kitegi
    Apr 4, 2015 at 21:13
  • $\begingroup$ That the number of primes that are generated gets smaller is an expected result. It would be interesting to compare the number of primes generated by this polynomial and the total number of primes below a given number N to see how many are missed by this polynomial. $\endgroup$
    – user25406
    Apr 4, 2015 at 23:50
  • $\begingroup$ At $n=3200$, $P(n)=10313623$, below that number, there are $683996$ primes, so the polynomial misses about $682721$ primes. $\endgroup$
    – Kitegi
    Apr 5, 2015 at 9:59
  • $\begingroup$ Thanks Farnight. The question now becomes "what is the best quadratic prime generating polynomial?",i.e. the one which generates the most primes below a given number N. I have a method to generate an infinite number of quadratic prime generating polynomials ( sadly I am not equipped to study them ) and will post it if there is an interest. $\endgroup$
    – user25406
    Apr 5, 2015 at 11:54

1 Answer 1

2
$\begingroup$

The question what quadratic polynomials can tell us about primes is very interesting, but also very difficult. Even the obvious question whether such a polynomial generates infinitely many primes, is not known in general. For details see the discussion on the Bunyakovsky conjecture. So we would expect that $p(n)=n^2+23n+23$ generates infinitely many primes.

$\endgroup$
2
  • $\begingroup$ does it mean that no quadratic polynomial, no matter what the coefficients are, will ever generate all primes? $\endgroup$
    – user25406
    Apr 4, 2015 at 23:53
  • $\begingroup$ Yes, you need polynomials in several variables to generate all primes, see here. $\endgroup$ Apr 5, 2015 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.