67 lines
1.9 KiB
Python
67 lines
1.9 KiB
Python
"""
|
|
Euler discovered the remarkable quadratic formula: n^2 + n + 41
|
|
|
|
It turns out that the formula will produce 40 primes for the consecutive integer values 0<=n<=39.
|
|
However, when n = 40, 40^2+40+41=40*(40+1)+41 is divisible by 41, and certainly when n = 41,
|
|
41^2+41+41 is clearly divisible by 41.
|
|
|
|
The incredible formula n^2-79n+1601 was discovered, which produces 80 primes for the consecutive values
|
|
0<=n<=79 . The product of the coefficients, -79 and 1601, is -126479 .
|
|
|
|
Considering quadratics of the form:
|
|
n^2+an+b , where |a|<1000 and |b|<=1000
|
|
where |n| is the modulus/absolute value of n
|
|
e.g. |11| = 11 and |-4| = 4
|
|
|
|
Find the product of the coefficients, a and b, for the quadratic expression that produces
|
|
the maximum number of primes for consecutive values of n, starting with n=0.
|
|
"""
|
|
|
|
from typing import Callable
|
|
|
|
|
|
def quadratic_primes(a: int, b: int) -> Callable[[int], int]:
|
|
return lambda n: n**2 + a * n + b
|
|
|
|
|
|
def is_prime(n: int) -> bool:
|
|
if n < 2:
|
|
return False
|
|
if n == 2:
|
|
return True
|
|
if n % 2 == 0:
|
|
return False
|
|
for i in range(3, int(n**0.5) + 1, 2):
|
|
if n % i == 0:
|
|
return False
|
|
return True
|
|
|
|
|
|
def max_prime_quadratic(a_max: int, b_max: int) -> tuple[int, int, int]:
|
|
max_primes = 0
|
|
max_a = 0
|
|
max_b = 0
|
|
for a in range(-a_max, a_max + 1):
|
|
for b in range(-b_max, b_max + 1):
|
|
primes = 0
|
|
n = 0
|
|
while is_prime(quadratic_primes(a, b)(n)):
|
|
primes += 1
|
|
n += 1
|
|
if primes > max_primes:
|
|
max_primes = primes
|
|
max_a = a
|
|
max_b = b
|
|
return max_a, max_b, max_a * max_b
|
|
|
|
|
|
def main():
|
|
a_max = 1000
|
|
b_max = 1000
|
|
max_a, max_b, product = max_prime_quadratic(a_max, b_max)
|
|
print(f"{max_a} x {max_b} = {product}.")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|