#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 77
# Author: David J. Oftedal.
# Find the lowest positive integer which can be written as the sum of primes in
# more than 5000 different ways.
$isprime = Hash.new(false)
class Integer
@@partitions = {}
# Break a number down into sums of primes.
#
# 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
partitions = @@partitions[self]
return partitions if partitions != nil
partitions = Hash.new(0)
(self-1).downto(1) do |firstnumber|
next if !firstnumber.prime?
remainder = self-firstnumber
decomposedremainder = remainder.partitions
partitions[firstnumber] = partitions[firstnumber] + 1 if remainder <= firstnumber and remainder.prime?
decomposedremainder.keys.each do |biggestremainder|
partitions[firstnumber] = partitions[firstnumber] + decomposedremainder[biggestremainder] if biggestremainder <= firstnumber
end
end
@@partitions[self] = partitions
return partitions
end
def partitionscount
dc = partitions.values
return 0 if dc.size == 0
return dc.inject(:+)
end
# Determine if self is prime.
def prime?
return true if $isprime[self]
return true if self == 2 || self == 3
# Fast mini-primality test
return false if (self-1) % 6 != 0 && (self+1) % 6 != 0
return false if self < 2
# Slow, but deterministic primality test
# If self is divisible by any smaller prime, it's not prime.
# Try 2 and 3, plus all possible primes 6n±1 up to and including the square root.
return false if self%2 == 0 || self%3 == 0
(6..(self**0.5).to_i + 1).step(6).each {|f| return false if (self % (f-1) == 0 || self % (f+1) == 0)}
$isprime[self] = true
true
end
end
if $0 == __FILE__
i = 3
loop do
if i.partitionscount > 5000
puts "The lowest positive integer which can be written as the sum of primes in more than 5000 different ways is " << i.to_s << "."
exit(0)
end
i += 1
end
end