Project Euler Problem #69

Problem #69 concerns multiplicative functions, and more specifically, Euler’s Totient Function. The question reads:

Once again, I apologize for not embedding this within WordPress. As it turns out, this problem can be done by hand with a little mathematical knowledge. Here’s my solution:

Solution #1: Mathematical Approach

This solution makes use of the fact that phi(n) is a multiplicative function. A function f on the natural numbers is called multiplicative if for all natural numbers m and n such that gcd(m,n) = 1, f(m)*f(n) = f(m*n). As it turns out, Euler’s Totient function phi(n) is a multiplicative function. As a result, the function F(n) = n/phi(n) is also a multiplicative function, because F(m)*F(n) = m*n/(phi(m)*phi(n)) = (m*n)/phi(m*n) = F(m*n). Thus, we can break this problem down into investigating the function for prime powers.

It is well known that phi(p^n) = (p-1)*p^(n-1) for primes p. Thus, F(p^n) = p/(p-1), regardless of the value of n. Thus, to maximize the value of F(n) while minimizing the value of n, it suffices to multiply n by all the distinct smallest possible values of p. (IE, the smallest primes) Doing this until a product greater than 1,000,000 is reached, we are finished. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Mathematical Approach to Project Euler Problem #69
 '''
 
 import time
 from math import sqrt
 
 def isPrime(n):
     if(n<=1):
         return False
     if(n<4):
         return True
     if(n%2==0):
         return False
     c = 3
     while(c<=sqrt(n)):
         if(n%c==0):
             return False
         c+=2
     return True
 
 def projectEulerProblemSixtyNine(n):
     total = 1
     c = 2
     while(total<=n):
         if(isPrime(c)):
             if(total*c>n):
                 return total
             total*=c
         c+=1
     return total
 
 start = time.time()
 print projectEulerProblemSixtyNine(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 510510
 --- 1.90734863281e-05 seconds ---
 
 for input of n = 1000000
 ''' 

And with that, we’re done. We easily could have done this problem by hand for small inputs such as 1,000,000. Even large inputs can be handled quite quickly.

Thanks for reading! See you tomorrow.