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