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

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?

P=Primes();
for b in range (0,1000000):
success=true;
for x in range (1,41):
if not (x^2-x+b) in P:
success=false;
break;
if success:
print b;

edit retag 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.

( 2020-05-19 15:43:29 -0500 )edit

Sort by » oldest newest most voted

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

more