I was playing around with numbers the other day and realized that the first few values for $n(n - 1) + 1$ are prime. Now, I also quickly realized that not all values are prime ($n = 5$ results in 21, which is not prime), but I also noticed that all of the values for which the formula doesn't result in a prime are odd. I wrote up a quick python script, and since checking $n < 100,000,000$ hasn't provided an even counterexample, I was wondering if I could somehow prove or disprove the hypothesis that, for all even $n$, $n^2 - n + 1$ is prime.

I am aware of Goldbach's proof (mention of it) that for any polynomial, not all of its outputs can be prime, but I don't think that applies if the input is restricted to to just even integers.

Python 3.6.7 code I used:

from math import sqrt
from itertools import count, islice


for n in islice(count(1), m):
    if (n % 2):
        p = 0
        q = n * (n - 1) + 1
        p = n > 1 and all(n % j for j in islice(count(2), int(sqrt(n) + 1)))
    if (p): print(n, p)

Link to source of method of checking primality.

  • 1
    $\begingroup$ $n=10?{{{{}}}}$ $\endgroup$ – Lord Shark the Unknown May 13 at 20:37
  • 1
    $\begingroup$ Goldbach's proof applies to $f(2n)$ too. $\endgroup$ – Bill Dubuque May 13 at 20:40
  • 1
    $\begingroup$ Or $n=8$. $\quad $ $\endgroup$ – lulu May 13 at 20:40
  • 1
    $\begingroup$ checking wether an integer is prime by using float point arithmetic is a bit risky $\endgroup$ – Adren May 13 at 20:40
  • 2
    $\begingroup$ If $p(n)$ is a polynomial with prime values at all the even integers then $q(n)=p(2n)$ is prime for all integers. $\endgroup$ – lulu May 13 at 20:42

This is not true. A simple search in Python gives counterexamples of $$n=8, 10, 12, 14, 20, 24, 26, 30, 32, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 62, 64, 66, 68,\dots$$ which have corresponding composite values of $$n^2-n+1=3\cdot19, 7\cdot13, 7\cdot19, 3\cdot61, 3\cdot127, 7\cdot79, 3\cdot7\cdot31, 13\cdot67, 3\cdot331, 13\cdot97, \dots$$

Here is the code I used by the way:

#Returns a list of all primes less than or equal to Max
def ListPrimes(Max):
    if Max <= 1:
        return []
    Primes = [True for i in range(Max+1)] 

    for PrimeIndex in range(2, Max+1): 
        if (Primes[PrimeIndex] == True):
            PrimeIndex2 = PrimeIndex * 2
            while(PrimeIndex2 <= Max): 
                Primes[PrimeIndex2] = False
                PrimeIndex2 += PrimeIndex
    return [p for p in Primes if p!= False][2:]

print([i for i in range(2,100,2) if not ((i*i-i+1) in ListPrimes(10000))])
  • $\begingroup$ Thanks, I was wondering if I was missing something. $\endgroup$ – IronEagle May 14 at 14:42

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