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/