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.
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/
