/*
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).
% 0.91s
euler27 =>
T = 999,
BestLen = 0,
BestA = 0,
BestB = 0,
foreach(A in -T..T, B in -T..T)
% Len = p2(A,B),
Len = 0,
PP = Len**2 + A*Len + B,
while (PP > 1, prime_cached(PP))
Len := Len + 1,
PP := Len**2 + A*Len + B
end,
if Len > BestLen then
BestLen := Len,
BestA := A,
BestB := B
end
end,
% println([besta=BestA,bestB=BestB,bestLen=BestLen, answer=BestA*BestB]).
println(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]]).
% 1.16s
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]).
% 1.18s
euler27d =>
T = 999,
L = [[Len,A*B] : A in -T..T, B in -T..T, Len = p2(A,B), Len > 0],
Max = max([X[1] : X in L]),
println([X : X in L, X[1] == Max]).
p2(A,B) = N =>
N1 = 0,
PP = N1**2 + A*N1 + B,
% PP := pp(A,B,N1),
while (PP > 1, prime_cached(PP))
N1 := N1 + 1,
PP := N1**2 + A*N1 + B
% PP := pp(A,B,N1) % N1**2 + A*N1 + B
end,
N = N1.
pp(A,B,N1) = N1**2 + A*N1 + B.
% just caching the built-in prime/1 function
table
prime_cached(N) => prime(N).