Euler Solution 69

From ProgSoc Wiki

Jump to: navigation, search

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)
Personal tools