#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 70
# Author: David J. Oftedal.
# See 069.rb for a more readable solution to a similar problem.
# Find the number between 1 and 10 000 000 with the minimum ratio of n/φ(n), for which φ(n) is a permutation of n.
$minphi = 0
$minnum = 0
$minratio = 2147483647 # 2**31 - 1
$mindiff = 2147483647
class Integer
@@factorcache = {}
# Eliminate some numbers that aren't square-free.
def possibly_squarefree?
[4, 9, 25, 36].each {|n| return false if self % n == 0}
return true
end
def permutation? n
return self.to_s.chars.sort == n.to_s.chars.sort
end
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)
# Continually check the ratio between (the outer) self and phi
# and abort if it's larger than the minimum ratio found.
return nil if (original_self.to_f / (numerator / denominator)) >= $minratio
@@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
# Give up if self isn't square-free, as
# there will be a square-free number with
# the same ratio.
if tmp % factor == 0
return nil
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__
10000000.downto(2) do |n|
# Skip numbers that aren't square-free,
# as there will be square-free numbers with
# the same ratio.
if !n.possibly_squarefree?
n -= 1
next
end
nphi = n.phi
if nphi == nil
n -= 1
next
end
# Check that the absolute difference between n and n.phi
# is less than the smallest one before calculating the
# ratio.
diff = n - nphi
if diff < $mindiff
# Then check that the ratio is smaller,
# and whether n and n.phi are permutations.
ratio = n.to_f / nphi
if ratio < $minratio && n.permutation?(nphi)
$minphi = nphi
$minratio = ratio
$mindiff = diff
$minnum = n
end
end
n -= 1
end
puts "The number between 1 and 10 000 000 with the minimum ratio of n/φ(n), for which φ(n) is a permutation of n, is " << $minnum.to_s << ". φ(n) is " << $minphi.to_s << ", and the ratio is " << $minratio.to_s << "."
end