MathJax

SyntaxHighlighter

Highlight

Custom CSS

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)
    set.add(p.to_i)
  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
Post a Comment