|
| 1 | +""" |
| 2 | +Euler discovered the remarkable quadratic formula: |
| 3 | +n2 + n + 41 |
| 4 | +It turns out that the formula will produce 40 primes for the consecutive values |
| 5 | +n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible |
| 6 | +by 41, and certainly when n = 41, 412 + 41 + 41 is clearly divisible by 41. |
| 7 | +The incredible formula n2 − 79n + 1601 was discovered, which produces 80 primes |
| 8 | +for the consecutive values n = 0 to 79. The product of the coefficients, −79 and |
| 9 | +1601, is −126479. |
| 10 | +Considering quadratics of the form: |
| 11 | +n² + an + b, where |a| < 1000 and |b| < 1000 |
| 12 | +where |n| is the modulus/absolute value of ne.g. |11| = 11 and |−4| = 4 |
| 13 | +Find the product of the coefficients, a and b, for the quadratic expression that |
| 14 | +produces the maximum number of primes for consecutive values of n, starting with |
| 15 | +n = 0. |
| 16 | +""" |
| 17 | + |
| 18 | +import math |
| 19 | + |
| 20 | + |
| 21 | +def is_prime(k: int) -> bool: |
| 22 | + """ |
| 23 | + Determine if a number is prime |
| 24 | + >>> is_prime(10) |
| 25 | + False |
| 26 | + >>> is_prime(11) |
| 27 | + True |
| 28 | + """ |
| 29 | + if k < 2 or k % 2 == 0: |
| 30 | + return False |
| 31 | + elif k == 2: |
| 32 | + return True |
| 33 | + else: |
| 34 | + for x in range(3, int(math.sqrt(k) + 1), 2): |
| 35 | + if k % x == 0: |
| 36 | + return False |
| 37 | + return True |
| 38 | + |
| 39 | + |
| 40 | +def solution(a_limit: int, b_limit: int) -> int: |
| 41 | + """ |
| 42 | + >>> solution(1000, 1000) |
| 43 | + -59231 |
| 44 | + >>> solution(200, 1000) |
| 45 | + -59231 |
| 46 | + >>> solution(200, 200) |
| 47 | + -4925 |
| 48 | + >>> solution(-1000, 1000) |
| 49 | + 0 |
| 50 | + >>> solution(-1000, -1000) |
| 51 | + 0 |
| 52 | + """ |
| 53 | + longest = [0, 0, 0] # length, a, b |
| 54 | + for a in range((a_limit * -1) + 1, a_limit): |
| 55 | + for b in range(2, b_limit): |
| 56 | + if is_prime(b): |
| 57 | + count = 0 |
| 58 | + n = 0 |
| 59 | + while is_prime((n ** 2) + (a * n) + b): |
| 60 | + count += 1 |
| 61 | + n += 1 |
| 62 | + if count > longest[0]: |
| 63 | + longest = [count, a, b] |
| 64 | + ans = longest[1] * longest[2] |
| 65 | + return ans |
| 66 | + |
| 67 | + |
| 68 | +if __name__ == "__main__": |
| 69 | + print(solution(1000, 1000)) |
0 commit comments