11 Mar 10 Project Euler : Problem 27 in Ruby

I've taken ill for the last two days, so I've been working on a couple Project Euler problems in between trips to the bathroom.

Problem #27

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.

Since you start with n = 0, you know that b always has to be prime in order to satisfy n = 0.

Next, if b must be prime, and all primes greater than 2 are odd, and we don't care about expressions resulting in less than 3 consecutive primes (example expression has 40), then we know that all values of a must be odd in order to satisfy n = 1!

I also suspect that for the number of consecutive primes we need to 'win', that we only need to look at negative values of a, but I'm having a heck of a time trying to prove it.

027.rb

require 'prime_generator'

# pre-calculate primes
MAX     = 1_000
primer  = Prime_Generator.new MAX
primes  = primer.stack
product = 0
highest = 0

# a must be odd
(0..MAX).each do |i|
  next if i & 1 == 0

  # b must be prime
  primes.each do |b|

    # a can be positive or negative
    [i,-i].each do |a|
      n = 0
      while n += 1 do
        break unless primer.is_prime?(n ** 2 + a * n + b)
      end

      if highest < n
        highest = n
        product = a * b
      end

    end
  end
end

puts product

And here's the prime generator I'm using:

prime_generator.rb

class Prime_Generator

  attr_reader :stack

  def initialize max = 3
    @stack  = [1,2,3]
    fill_to max
  end

  def fill_to max
    n = 1
    while true do
      n += 4
      return @stack if n > max
      @stack << n if is_prime? n

      n += 2
      return @stack if n > max
      @stack << n if is_prime? n
    end
  end

  def is_prime? n
    return false if n <= 0
    max = Math.sqrt(n).floor
    fill_to(max + 1) if max > @stack.last

    @stack.each do |i|
      next if i == 1
      return true if i > max
      return false if n % i == 0
    end

    true
  end

end

You can find more Project Euler solutions here: https://svn2.assembla.com/svn/joe-zack-personal/projects/euler/ruby/

Tags: project euler, ruby