I kept trying to make this problem harder than it actually was, but ultimately a simple greedy solution worked just fine.

I would have saved myself a lot of time by actually solving the problem before attempting to optimize. C’est la vie!

Problem #29

Investigating combinations of English currency denominations.

def count_coins coins, target, last_coin = 0

	return 1 if target == 0
	total = 0

	coins.each do |c|
		next if c < last_coin
		total += count_coins(coins, target - c, c) if (target >= c)
	end

	total
end

puts count_coins(
	[1,2,5,10,20,50,100,200],
	200
)

I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.

Ruby even minds the big numbers for me, so the solution is quite trivial:

Problem #29

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

MIN, MAX = 2,100
values = []

(MIN..MAX).each do |base|
  (MIN..MAX).each do |power|
    values << base**power
  end
end

puts values.uniq.length

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/