#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 76
# Author: David J. Oftedal.
# Find the number of ways 100 can be written as a sum of at least two positive integers.
class Integer
@@partitions = {}
# Break a number down into sums of other numbers.
#
# The number is broken into down two parts: One which is not decomposed,
# and one which is further broken down, as long as the number it
# begins with is not larger than the first number.
#
# To save memory, only store the COUNTS of partitions and the
# numbers they begin with rather than the partitions themselves.
# The original algorithm is commented out where changes have been made.
def partitions
return {1=>1} if self == 2
partitions = @@partitions[self]
return partitions if partitions != nil
partitions = Hash.new(0)
(self-1).downto(1) do |firstnumber|
remainder = self-firstnumber
decomposedremainder = remainder.partitions
partitions[firstnumber] = partitions[firstnumber] + 1 if remainder <= firstnumber
decomposedremainder.keys.each do |biggestremainder|
partitions[firstnumber] = partitions[firstnumber] + decomposedremainder[biggestremainder] if biggestremainder <= firstnumber
end
end
@@partitions[self] = partitions
return partitions
end
def partitionscount
return partitions.values.inject(:+)
end
end
if $0 == __FILE__
puts "The number of different ways 100 can be written as a sum of at least two positive integers is " << 100.partitionscount.to_s << "."
end