#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 108
# Author: David J. Oftedal.
# Find a number that can generate more than 1000 diophantine reciprocals.
class Integer
def prime_factors
return prime_factors_recursive({})
end
# Factorization by trial division.
def prime_factors_recursive primefactors
isqrt = (self**0.5).to_i
(2..isqrt).each do |i|
if self % i == 0
primefactors[i] = true
(self/i).prime_factors_recursive(primefactors)
return primefactors
end
end
primefactors[self] = true if self > 1
return primefactors
end
def find_reciprocals
solutions = 0
(self+1..self+self).each do |denominator|
solutions += 1 if (Rational(1, self) - Rational(1, denominator)).numerator == 1
end
return solutions
end
end
# The most composite numbers tend to have the most solutions.
# Check only numbers with an ever-increasing number of prime factors.
num = 1
maxfactors = 1
loop do
numfactors = num.prime_factors.count
if numfactors >= maxfactors
maxfactors = numfactors
solutions = num.find_reciprocals
if solutions > 1000
puts "The number " << num.to_s << " has " << solutions.to_s << " reciprocals."
exit(0)
end
end
num += 1
end