Project Euler Problem 70 Solution

Question

Euler’s Totient function, \varphi(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, \varphi(9)=6. The number 1 is considered to be relatively prime to every positive number, so \varphi(1)=1.

Interestingly, \varphi(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 \lt n \lt 10^7, for which \varphi(n) is a permutation of n and the ratio \frac{n}{\varphi(n)} produces a minimum.

Haskell

import Data.List (sort)

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
                      where (h, t) = span (< p*p) xs

permutation :: Int -> Int -> Bool
permutation x y = sort (show x) == sort (show y)

totient :: Int -> Int -> Int
totient p1 p2 = (p1 - 1) * (p2 - 1)

candidates :: [(Int, Int)]
candidates = [(n, phi) | p1 <- ps, p2 <- dropWhile (<= p1) ps, let n = p1 * p2, n <= 10000000, let phi = totient p1 p2]
    where ps = take 500 primes

main :: IO ()
main = print $ snd $ minimum [(fromIntegral n / fromIntegral phi, n) | (n, phi) <- candidates, permutation n phi]

$ ghc -O2 -o totient-permutation totient-permutation.hs
$ time ./totient-permutation
real   0m0.067s
user   0m0.067s
sys    0m0.000s

Python

#!/usr/bin/env python
from math import sqrt
from operator import mul
from itertools import *

def primes(n): 
    if n == 2:
        return [2]
    elif n < 2:
        return []
    sieve = list(range(3, n+1, 2))
    mroot = n ** 0.5
    half = (n + 1) // 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if sieve[i]:
            j = (m * m - 3) // 2
            sieve[j] = 0
            while j < half:
                sieve[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2] + [p for p in sieve if p]

def main():
    pairs = combinations(primes(2 * int(sqrt(1e7))), 2)
    minimum = (100, 0)
    for n, t in ((a * b, (a-1) * (b-1)) for a, b in pairs if a * b < 1e7):
        ratio = float(n) / t
        if ratio < minimum[0] and sorted(str(n)) == sorted(str(t)):
            minimum = (ratio, n)

    print(minimum[1])

if __name__ == "__main__": main()

$ time python3 totient.py
real   0m0.480s
user   0m0.479s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
require 'mathn'

min = [100, 0]
primes = (1..(2*Math.sqrt(1e7))).select { |n| n.prime? }
primes.combination(2).select { |a, b| a * b < 1e7 }.each do |a, b|
  n = a * b
  t = (a - 1) * (b - 1)
  if n.to_s.split('').sort == t.to_s.split('').sort
    if n / t < min[0]
      min = [n / t, n]
    end
  end
end
puts min[1]

$ time ruby totient.rb
real   0m2.918s
user   0m2.902s
sys    0m0.016s