/* Euler #27 in Picat. """ Euler published the remarkable quadratic formula: n^2 + n + 41 It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41^2 + 41 + 41 is clearly divisible by 41. Using computers, the incredible formula n^2 − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 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. """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ main => go. go => time(euler27). % 1.1s euler27 => T = 999, BestLen = 0, BestA = 0, BestB = 0, foreach(A in -T..T, B in -T..T) Len = p2(A,B), if Len > BestLen then BestLen := Len, BestA := A, BestB := B end end, println([besta=BestA,bestB=BestB,bestLen=BestLen, answer=BestA*BestB]). % 7.6s euler27b => T = 999, L = [[Len,A*B,A,B] : A in -T..T, B in -T..T, Len = p2(A,B)].sort_down(), M = L[1], writeln([len=M[1],value=M[2],a=M[3],b=M[4]]). euler27c => T = 999, BestLen = 0, BestA = 0, BestB = 0, foreach(A in -T..T, B in -T..T, Len = p2(A,B), Len > BestLen) BestLen := Len, BestA := A, BestB := B end, println([besta=BestA,bestB=BestB,bestLen=BestLen, answer=BestA*BestB]). p2(A,B) = N => N1 = 0, PP = N1**2 + A*N1 + B, while (PP > 1, prime_cached(PP)) N1 := N1 + 1, PP := N1**2 + A*N1 + B end, N = N1. % just caching the built-in prime/1 function table prime_cached(N) => prime(N).