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.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

Questions? Comments? Send me an email: z@chdenton.com