So I could have kept calculating the totient function directly and left it to run for years. Instead, I googled totient and discovered an interesting little mathematical quirk that would enable me to significantly reduce my testing set.

If a number is a product of two prime numbers …

then the totient of that number is …

- phi (n) = (p1-1) * (p2-1)

The square root of 10E7 is about 3100 plus change. So I calculated all the prime numbers 30% above and below that number. Then tested each of those numbers whereby the products were < 10E7. Smallest n/phi(n) wins. Routine runs in about 5 minutes. By the way, I wrote this routine to leverage (and re-learn Pythonian OOP).

#Euler70
from math import sqrt
class Algorithms:
def permutate(self, sequence):
if not sequence:
return [sequence]
else:
set = []
for k in range(len(sequence)):
part = sequence[:k] + sequence[k+1:]
for m in self.permutate(part):
set.append(sequence[k:k+1] + m)
return set
def primeGen (self, lowerLimit, upperLimit):
isPrime = [False, True]
i = 2
while i < upperLimit:
isPrime.append(True)
i += 1
p = 2
while p * p < upperLimit:
if isPrime[p] == True:
m = p * p
while m < upperLimit:
if m % p == 0:
isPrime[m] = False
m += p
p += 1
P = []
count = 0
for p in isPrime:
if p and count >= lowerLimit :
P.append(count)
count += 1
return P
class Problem70:
def __init__(self, limit):
self.limit = limit
self.Euler = Algorithms()
def Solution(self):
primes = self.Euler.primeGen(.7 * sqrt(self.limit), 1.3 * sqrt(self.limit))
print "Primes:"+str(primes)+"\n"
i = 0
minNDivPhi = 10
minN = 0
for p1 in primes:
print "Testing:"+str(p1)
i += 1
for p2 in primes[i:]:
n = p1 * p2
if n > self.limit:
break
phi = (p1-1) * (p2-1)
nDivPhi = n / float(phi)
if nDivPhi < minNDivPhi:
if str(int(n)) in self.Euler.permutate (str(int(phi))):
minNDivPhi = nDivPhi
minN = n
print "n:"+str(n)+" phi:"+str(phi)+" nDivPhi:"+str(nDivPhi)
return "Value of n where nDivPhi is minimized:"+str(minN)
if __name__ == '__main__':
P = Problem70(10000000)
print P.Solution()

### Like this:

Like Loading...

*Related*