MathJax

Syntax Highlighter CSS (shCore.css)

Syntax Highlighter CSS (shThemeDefault.css)

Syntax Highlighter JS (shCore.js)

Syntax Highlighter JS (shAutoloader)

Highlight CSS (default.css)

Highlight JS (highlight.pack.js)

Syntax Highlighter CSS (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