Find quadratic polynomial such that f(x)=x^2+ax+b is prime

savecancel

Homeworks tend to lose interest after some weeks, because solutions are provided... So i was waiting some time...

Here is a piece of code, which - given a lower bound $k$, say $k=70$, - is searching for polynomials of the shape $$f(X) =X^2 +aX+p\ ,$$ so that $f(j)$ is a prime number for all $j$ in the interval from $0$ top $k$. In particular, the numbers $f(0)=p$ and $f(1)=1+a+p=q$ are prime numbers. And these numbers are the strarting point for the search.

The tuple $(p,q)$ determines, $a$, so also the polynomial $f$, and we check in all cases if the needed values $f(0)=p$, $f(1)=q$, $f(2)$, ... , $f(k)$ are prime numbers. If yes, we record this polynominal. The search is done by searching in a fixed range PRIMES for the first two primes $p,q$.

Code:

FIRST_TWO_PRIMES_UPPER_BOUND = 10000
var('X');

k      = 70
count  = 0
pols   = []
PRIMES = list(primes(FIRST_TWO_PRIMES_UPPER_BOUND))

for p in PRIMES:
    count += 1
    if count % 100 == 0:
        print(f"count = {count} :: checking prime {p}...")
    # we are searching for a polynomial of the shape x^2 + ax + p, a>0, with prime values on [0..k]
    for q in PRIMES:
        q_works = True # so far
        a = q - p - 1
        for j in [2..k]:
            if not ZZ(j^2 + a*j + p).is_prime():
                q_works = False
                # print(p, 'FAILS FOR', q, a, j, (j^2 + a*j + p).factor())
                break
        if q_works:
            pol =  X^2 + a*X + p
            print(f"!!! Found polynomial: {pol} !!!")
            pols.append(pol)

if pols:
    print(f"SOLUTIONS FOR k = {k}:")
    for pol in pols:
        print(pol)
else:
    print(f"NO SOLUTIONS FOR k = {k}:")

And here are the found solutions for $k=70$:

SOLUTIONS FOR k = 70:
X^2 - 61*X + 971
X^2 - 63*X + 1033
X^2 - 65*X + 1097
X^2 - 67*X + 1163
X^2 - 69*X + 1231
X^2 - 71*X + 1301
X^2 - 73*X + 1373
X^2 - 75*X + 1447
X^2 - 77*X + 1523
X^2 - 79*X + 1601

The last polynomial, $X^2 -79X +1601=X(X-79)+1601$ takes the same values in the points $j$ and $79-j$, so we obtain prime values (with repetitions) even for all $j$ from $0$ to $79$.