Problem 70

Resources

The page on wikipedia about euler’s totient was really helpful.

Comments

This problem was great! I realized, from reading the wikipedia article on euler’s totient, that the smallest ratio of n/φ(n) will be one when n is prime. For prime numbers, φ(n) = n-1, so there was no need for me to use the φ function at all.

There is no way that φ(n) could be a palendrome of n because φ(n) = n-1. This told me that the next best way for n/φ(n) to be minimized was if n was the product of just two primes.

So, I generated a list of all the primes listed in ordered pairs with their φ(n). I then used the combinations iterator to generate all pairs of those primes until I found the smallest value.

Code

def isperm(n, m):
	n = sorted(map(int, str(n)))
	m = sorted(map(int, str(m)))
	if n == m:
		return True
	else:
		return False

def isprime(n):
	if n == 0 or n == 1: return False
	for i in range(2, int(n**0.5 + 1)):
		if n%i == 0: return False
	return True


n = 1
primes = []
ratio = [10**7, 10**7]

while n <= 10**7/2:
	n += 1	
	if isprime(n) == True: 
		primes.append([n, n-1])

from itertools import combinations

for pairs in combinations(primes, 2):
	n = pairs[0][0]*pairs[1][0]
	if n >= 10**7:
		continue
	ph = pairs[0][1]*pairs[1][1]
	nph = n/float(ph)
	if isperm(n, ph) == True and nph < ratio[1]:
		ratio = [n, nph]
		print ratio
		
print ratio