#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 72
# Author: David J. Oftedal.
# Find the number of possible reduced proper fractions whose denominator ≤ 1 000 000.
class Integer
@@factorcache = {}
def phi
return phi_recursive(self.to_f, self, 1)
end
# Calculate phi using factorization by trial division.
def phi_recursive(original_self, numerator, denominator)
# See if a factor for this number was found previously.
# If so, skip the factorization step.
factor = @@factorcache[self]
cached = true if factor != nil
# See if self is divisible by 2.
if factor == nil && self & 1 == 0
factor = 2
elsif factor == nil && self % 3 == 0
factor = 3
end
# See if self is divisible by the possible primes
# 6k±1 up to and including the integer square root.
if factor == nil
isqrt = (self**0.5).to_i
(5..isqrt).step(6) do |i|
if self % i == 0
factor = i
break
end
if self % (i+2) == 0
factor = (i+2)
break
end
end
end
# Self must be a prime if no factor has been found.
factor = self if factor == nil
# If (the outer) self is a prime, φ(self) is self - 1.
return self - 1 if factor == original_self
if factor > 1
# Continually calculate phi.
numerator *= (factor-1)
denominator *= (factor)
@@factorcache[self] = factor if cached != true
# Factor must be a prime, if it's the lowest factor found,
# but self / factor may be composite.
if factor != self
tmp = self / factor
while tmp % factor == 0
tmp = tmp / factor
end
# self/factor must be a factor, too. Keep factoring that.
return tmp.phi_recursive(original_self, numerator, denominator)
end
end
return numerator / denominator
end
end
if $0 == __FILE__
# The number of possible reduced proper fractions with one denominator is equal
# to the number of integers less than that denominator that are coprime to it.
sum = 0
1000000.downto(2) do |denominator|
sum += denominator.phi
end
puts "The number of possible reduced proper fractions whose denominator ≤ 1 000 000 is " << sum.to_s << "."
end