Project Euler Problem 70 Solution

Question

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

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

Find the value of nn, 1<n<1071 \lt n \lt 10^7, for which φ(n)\varphi(n) is a permutation of nn and the ratio nφ(n)\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.086s
user   0m0.084s
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.387s
user   0m0.384s
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   0m3.314s
user   0m3.308s
sys    0m0.004s