Python Implementation of Problem 27

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 27

Another good problem for code golf

Problem: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.

python.src.p0027.main() → int
 1"""
 2Project Euler Problem 27
 3
 4Another good problem for code golf
 5
 6Problem:Euler discovered the remarkable quadratic formula:
 7
 8n**2+n+41
 9
10It turns out that the formula will produce 40 primes for the consecutive
11integer values 0≤n≤39. However, when ``n=40``, ``40**2+40+41=40(40+1)+41`` is divisible
12by 41, and certainly when ``n=41``, ``41**2+41+41`` is clearly divisible by 41.
13
14The incredible formula ``n**2−79n+1601`` was discovered, which produces 80 primes
15for the consecutive values 0≤n≤79. The product of the coefficients, −79 and
161601, is −126479.
17
18Considering quadratics of the form:
19
20    n**2+an+b
21
22, where ``|a|<1000`` and ``|b|≤1000``
23
24where ``|n|`` is the modulus/absolute value of n, e.g. ``|11|=11`` and ``|−4|=4``
25
26Find the product of the coefficients, a and b, for the quadratic expression
27that produces the maximum number of primes for consecutive values of n,
28starting with n=0.
29"""
30from functools import partial
31from itertools import count, takewhile
32
33from .lib.math import quadratic
34from .lib.primes import is_prime, primes_and_negatives
35
36
37def main() -> int:
38    streak = answer = 0
39    for a in range(-999, 1000):
40        for b in primes_and_negatives(1001):
41            formula = partial(quadratic, a=a, b=b)
42            test = sum(1 for _ in takewhile(is_prime, map(formula, count())))
43            if test > streak:
44                streak = test
45                answer = a * b
46    return answer

Tags: sequence-generator, prime-number, quadratic-equation, python-iterator