#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 78
# Author: David J. Oftedal.
# Find the lowest number of coins that can be divided into piles in a number of
# ways that is divisible by one million.
# Solved by using the formula at https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Recurrence_formula .
# Generators that will yield infinite streams of generalized pentagonal numbers.
class GeneralizedPentagonalGenerator
include Enumerable
# Start at n.
def initialize n
@current = n
end
def each
loop do
yield(@current.pentagonal)
yield((-@current).pentagonal)
@current += 1
end
end
end
class Integer
# Return pentagonal number self
def pentagonal
((3*self**2)-self)/2
end
@@partitions = [1]
def partitions
return 0 if self < 0
return 1 if self < 2
return @@partitions[self] if @@partitions[self] != nil
sum=0
i = 0
GeneralizedPentagonalGenerator.new(1).take_while{|pentagonal_number| self-pentagonal_number >= 0}.each_with_index do |pentagonal_number, i|
sum += (self-pentagonal_number).partitions if (i%4) < 2
sum -= (self-pentagonal_number).partitions if (i%4) >= 2
end
sum %= 1000000
@@partitions << sum
return sum
end
end
if $0 == __FILE__
i = 1
t = 0
loop do
partitions = i.partitions
puts i.to_s << "\t" << partitions.to_s
if partitions == 0
puts "The lowest number of coins that can be divided into piles in a number of ways that is divisible by one million is " << i.to_s << "."
exit(0)
end
i += 1
end
end