Ask Your Question

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

asked 2020-05-19 16:15:46 +0200

Jenny123 gravatar image

updated 2020-05-21 13:06:42 +0200

a. Find quadratic polynomial f(x)=x²+ax+b , a,b ∈ℤ such that f(x) is prime for 1≤n≤40

I know that the polynomial f(x)=x²-x+41 takes prime values for all 1≤n≤40. But how can I find this polynomial with sage?

b. Find k (as large as possible) and quadratic polynomial such that f(x)=x²+ax+b (a,b ∈ℤ) is prime for 1≤n≤k

I only find can b if I know a. But how can I find both?

for b in range (0,1000000):
     for x in range (1,41): 
          if not (x^2-x+b) in P:
     if success:
         print b;
edit retag flag offensive close merge delete


This looks like homework. If you want some help, you should ask more precise questions related to your research in solving those exercises, especially where you are locked.

tmonteil gravatar imagetmonteil ( 2020-05-19 22:43:29 +0200 )edit

1 Answer

Sort by » oldest newest most voted

answered 2020-06-12 17:48:51 +0200

dan_fulea gravatar image

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$.



k      = 70
count  = 0
pols   = []

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())
        if q_works:
            pol =  X^2 + a*X + p
            print(f"!!! Found polynomial: {pol} !!!")

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

And here are the found 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$.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2020-05-19 16:15:46 +0200

Seen: 199 times

Last updated: Jun 12 '20