## Wednesday, February 3, 2010

### Project Euler #27: Quadratic primes

Here is problem #27.

Again, judicious application of elementary number theory can reduce the search space.

First, notice that the restriction that $$f(0)$$ is a prime immediately constrains $$b$$ to be a prime.

Furthermore, $$f(b)$$ is definitely NOT a prime, as:

$$f(b) = b^2 + ab + b$$
$$f(b) = b(b + a + 1)$$

When considering a polynomial, then, $$0 <= n <= b$$, $$-1000 < a < 1000$$, and $$b$$ must be prime. We are given that for values of $$b \approx 1601$$, only 80 consecutive primes are produced, so the search space is already thinning with this very naive analysis.

Further analysis could probably tighten the bounds on $$a$$, but with just these bounds, a solution can be found in under 10 seconds.

Using a precomputed list of primes, this Ruby program finds the solution in approximately 6 seconds:

def f(n, a, b)
n*n + a*n + b
end

def count(ps, a, b)
(0..b).take_while { |n| t = ps.include? f(n, a, b) }.count
end

def primes
# Grab a file of the first few primes to make calculation
# easier.
file = File.new("primes.txt")
set = Set.new
while (p = file.gets)
end
file.close
set
end

b_max   = 1000
ps      = primes
bs      = ps.take_while { |b| b <= b_max }
bs      = bs + bs.map { |b| -b }
a, b, c = 0, 0, 0

bs.each do |b_i|
(-b_max..b_max).each do |a_i|
c_i = count(ps, a_i, b_i)
if c_i > c
a, b, c = a_i, b_i, c_i
end
end
end

puts a*b