Problem #70 concerns Euler’s Totient Function again. The problem reads:
Project Euler Problem 70: Totient permutation
Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
My solution for this problem is quite bad as it takes longer than a minute to run. Thus, I will definitely return to this problem at some point. Here is my solution:
Solution #1: Bad Sieve Approach
We determine the value of Euler’s Totient Function for every value of n less than 1,000,000 with a sieve. We know that for all values of n and all primes p, phi(p*n) = p*phi(n) if n is divisible by p and phi(p*n) = (p-1)*phi(n) otherwise. Thus, we determine the value of the totient function for each number, working our way up with this approach. Once we’re done, we determine the ones that are permutations of the digits of the input and store the one with the maximum value of n/phi(n). Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Semi-Dynamic Approach to Project Euler Problem #70
'''
import time
from math import sqrt
def isPermutation(a,b):
return sorted(str(a)) == sorted(str(b))
def projectEulerProblemSeventy(n):
totients = [1,1]
minNumerator = -1
minDenominator = 1
for x in range(2,n+1):
v = -1
if(x%2==0):
if(x%4==0):
v = totients[x/2]*2
else:
v = totients[x/2]
else:
c = 3
myRoot = sqrt(x)
while(c<=myRoot):
if(x%c==0):
if(x%(c*c)==0):
v = totients[x/c]*c
else:
v = totients[x/c]*(c-1)
break
c+=2
if(c>myRoot):
v = x-1
totients.append(v)
if(x%9==v%9):
if(isPermutation(x, v)):
if(minNumerator == -1):
minNumerator = x
minDenominator = v
elif(minNumerator*v>minDenominator*x):
minNumerator = x
minDenominator = v
return minNumerator
start = time.time()
print projectEulerProblemSeventy(10000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
8319823
--- 66.285148859 seconds ---
for input of n = 10000000
'''
And with that, we’re done. As stated above, this solution is very bad, as it takes over a minute to run in Python 2.7 on a decent computer. Thus, I will definitely return to this problem at some point to search for a better solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 