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.

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.089s
user   0m0.088s
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.475s user 0m0.464s 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.571s
user   0m3.504s
sys    0m0.028s