# HG changeset patch # User Steve Losh # Date 1487784397 0 # Node ID 404d59f863aa0af4571aca40f63cb02f253b0ead # Parent d84ef3399dd13da1bbcc9800e749ec3be3a56618 Problem 27 diff -r d84ef3399dd1 -r 404d59f863aa src/euler.lisp --- a/src/euler.lisp Wed Feb 22 17:13:41 2017 +0000 +++ b/src/euler.lisp Wed Feb 22 17:26:37 2017 +0000 @@ -738,6 +738,38 @@ (for i :in (set-difference (primes-below 1000) '(2 5))) (finding i :maximizing (multiplicative-order 10 i)))) +(defun problem-27 () + ;; Euler discovered the remarkable quadratic formula: + ;; + ;; n² + 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² + 40 + 41 = 40(40 + 1) + ;; + 41 is divisible by 41, and certainly when n=41, 41² + 41 + 41 is clearly + ;; divisible by 41. + ;; + ;; The incredible formula n² − 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² + 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. + (flet ((primes-produced (a b) + (iterate (for n :from 0) + (while (primep (+ (square n) (* a n) b))) + (counting t)))) + (iterate (for-nested ((a :from -999 :to 999) + (b :from -1000 :to 1000))) + (finding (* a b) :maximizing (primes-produced a b))))) + ;;;; Tests -------------------------------------------------------------------- (def-suite :euler) @@ -768,6 +800,7 @@ (test p23 (is (= 4179871 (problem-23)))) (test p24 (is (= 2783915460 (problem-24)))) (test p25 (is (= 4782 (problem-25)))) +(test p26 (is (= 983 (problem-26)))) ;; (run! :euler)