# Euler Solution 70

(Difference between revisions)
 Revision as of 06:27, 7 May 2009 (view source)← Older edit Latest revision as of 00:27, 25 April 2010 (view source)Althalus (Talk | contribs) (→Solutions for Problem 70) Line 56: Line 56: - whose n and phi(n) do not share digits, then take the smallest n/phi(n). -} - 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))) 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 + + [[Category: Euler]] [[Category: Euler]]

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

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