Euler Solution 70

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 70

Given that the Euler Totient function of n is phi(n), find the n in the range 2..107 where the digits of n are a permutation of phi(n) and n/phi(n) is minimal.

Haskell by SanguineV

Runtime: 161.940 ms

import Data.List

{- Primes -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'         = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Convert a numerator and denominator into a double -}
conv :: Integer -> Integer -> Double
conv n  d = (fromIntegral n) / (fromIntegral d)

{- Determine if two strings are permutations of each other. -}
perms :: [Char] -> [Char] -> Bool
perms l r | not (length l == length r) = False
perms l r = [] == foldl (\x y -> delete y x) l r

{- Here is where it gets tricky, observe that primes will be the closest to
 - having n/phi(n) == 1. Unfortunately a prime by itself will not have the
 - digits of n and phi(n) the same (as phi(n) for a prime is n - 1).
 - Also note the larger the prime, the closer to 1, so we are looking for
 - the product of two primes.
 - With this in mind, given a limit, generate a list of (prime * prime)'s 
 - using large prime numbers. Also generate the phi(n) values for these as
 - it is each to do here (recall phi(a*b) == phi(a) * phi(b) ). -}
pps :: Integer -> [(Integer,Integer)]
pps lim = inner (dropWhile (< div sqrtlim 2) primes)
  where
    sqrtlim  = floor (sqrt (fromIntegral lim))
    inner :: [Integer] -> [(Integer,Integer)]
    inner (p:ps) | p > sqrtlim = []
    inner (p:ps) = (takeWhile (\(x,y) -> x < lim) 
                         (map (\x -> (x * p,(x - 1) * (p - 1))) ps)) ++ (inner ps)

{- Given a list of n's and phi(n)'s, find the one with the smallest n/phi(n). -}
findIt :: [(Integer,Integer)] -> Integer
findIt l = inner 1 10 l
  where
    inner :: Integer -> Double -> [(Integer,Integer)] -> Integer
    inner n r [] = n
    inner n r ((i,pi):xs) | conv i pi < r = inner i (conv i pi) xs
    inner n r (x:xs) = inner n r xs

{- Generate some candidate (prime * prime)'s below the limit, filter out the ones
 - whose n and phi(n) do not share digits, then take the smallest n/phi(n). -}
main = print (findIt (filter (\(x,y) -> perms (show x) (show y)) (pps 10000000)))

Python by Althalus

RUntime: 4 seconds.

from primeFunctions import genPrimes
from itertools import product
from time import time
start = time()

def compare(n1,n2):
    n1s = list(str(n1))
    n2s = list(str(n2))
    n1s.sort()
    n2s.sort()
    if n1s == n2s: return True
    return False

# Big primes will be the closest to 1 for p/phi(p), since the 
# difference between p and phi(p) is pretty much negligible, but 
# primes will never be permutations of their phi(p) values.
# product of two primes should still be relatively close to 1 for n/phi(n)
# compared to normal numbers.
# phi(p) = p-1 and phi(pq) = phi(p) * phi(q) so products of primes is good for
# the math too.
# Obviously we need to keep our products of primes below the limit,
# and the bigger the primes, the smaller the n/phi(n).

limit = 10**7
minimum = 1000000
ans = 0
primes = genPrimes(int((limit**0.5)*2))
for pp in product(primes[100:], repeat=2):
    n = pp[0]*pp[1]
    if n > limit: continue
    phi_n = (pp[0]-1)*(pp[1]-1)
    if compare(n,phi_n):
        div = float(n)/phi_n
        if div < minimum:
            minimum = div
            ans = n

print ans
print time()-start
Personal tools