# Euler Solution 70

### From ProgSoc Wiki

(Difference between revisions)

(→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]] |

## Latest revision as of 00:27, 25 April 2010

# Solutions for Problem 70

Given that the Euler Totient function of *n* is *phi(n)*, find the *n* in the range 2..10^{7} 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