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.
We can reduce our search significantly by selecting prime pairs (p1, p2 ) and calculate n as n = p1 x p2. This allows the totient to be calculated as
The range of primes was selected by taking the square root of the upper bound, 10,000,000, which is about 3162 and taking ±30% for a range of primes from 2000 to 4000 (247 primes).
Runs < 1 second in Python.
from Euler import prime_sieve, is_perm, sqrt L = 10**7 primes = prime_sieve(int(1.30*sqrt(L))) del primes[:int(0.6*len(primes))] def pe70(limit): min_q, min_n, i = 2, 0, 0 for p1 in primes: i+=1 for p2 in primes[i:]: if (p1+p2)%9 != 1: continue n = p1 * p2 if n > limit: return min_n phi = (p1-1) * (p2-1) q = n / float(phi) if is_perm(phi, n) and min_q>q: min_q, min_n = q, n return "NFI!" print "Answer to PE70 = ",pe70(L)
- The result for 109 was 990326167 < 1 second and 1010 was 9996217801 < 4 seconds.
- The line:
if(p1+p2)%9 != 1: continueis an optimization that observes for two integers to be permutations of one another their difference must be a multiple of 9.
- The referenced functions are on the tools page.