# Euler Solution 69

### From ProgSoc Wiki

# Solutions for Problem 69

Find n <= 1000000 with the maximum n/phi(n), where phi(n) is Euler's Totient function.

## Haskell by SanguineV

Runtime: 8.716 ms

{- Generate 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 {- Generate primorials -} primorials = map (\x -> product (take x primes)) [1..] {- The primorials have the smallest phi(n) relative to n, this they will be the - maximum of n/phi(n). Find the largest primorial less than the limit -} main = print (last (takeWhile (< 1000000) primorials))

This has similarities to problem 243, so use that solution/knowhow to solve this one.

## Python by Althalus

Runtime: 43ms

My comments don't make much sense to me, tho they did when i wrote them. At least I understand Euler's totients now. Maybe the comments will be somewhat useful to anyone who looks at it. Some patches are earlier attempts that weren't fast enough or didn't work. Don't know, didn't have hours to let those versions run.

#!/usr/bin/python #The totient is the total of relatively prime numbers less than n. #IE, the total of all numbers less than n wich are neither factors of, nor share any factors of, n. import time import math start_time = time.time() #Function for Highest Common Factor. def hcf(f): n,d=f while n: n,d=d%n,n return d #Function to find the totient. Do so by checking the HCF of every number. #This version takes 6 seconds to find the totient of 1000000. TOO SLOW. def phi(n): i = 1 counter = 0 while i < n: :set nonu #If the HCF is 1, it is relatively prime. if hcf((i,n))==1: counter +=1 i+=1 return counter file = open(r'/home/justin/euler/primes.txt','r') primes = [int(i) for i in file.readlines()] file.close() def getPrimeFactors(n): primeFactors = [] for i in primes: if i > math.sqrt(n)+1: break if n%i == 0: #Don't want double ups in the list of prime factors for this solution. if i not in primeFactors: primeFactors.append(i) if n/i in primes and n/i not in primeFactors: primeFactors.append(n/i) return primeFactors #Totient is related to the prime factors of a number. WIth this in mind, trying to write a more efficient method. def phi2(n): #first we get a list of prime factors. primes = getPrimeFactors(n) #phi(x)=x*(1-1/p1)...(1-1/pn) totient=n for p in primes: totient *= (1.0-(1.0/p)) return totient max = 0 nm = 0 #for n in range(1,1000001): # m_test = n/phi2(n) # if m_test > max: # max=m_test # nm=n # # Above approach would have taken a day at least. Why check all of them? # The ones with lots of prime factors have the best chance of success. n=1 for p in primes: n*=p if n >= 1000000: break m_test = n/(phi2(n)) if m_test > max: max=m_test nm=n print nm run_time = time.time() - start_time print (run_time)