Project Euler 70 - Totient Permutation

Official link:

Thought Process

In Problem 69 we were looking to maximize n/φ(n), now we are looking to minimize so let's reverse the logic

Now let's notice 3 key facts which help speed up the problem greatly

  1. We are looking for the least amount of prime factors, but we cannot have just one because let's say it is a prime,p then p/φ(p) = p/(p-1), and clearly p-1 and p cannot be permutations of each other

  2. We will now look for 2 primes, in order to minimize n/φ(n) we want to maximize φ(n) and minimize n, this implies that the 2 prime factors sshould both be near sqrt(10,000,000) ~3126

  3. Using the 2nd way to calculate φ(n) from Eulers Totient Function we see that if n=pq where p, q are primes, then φ(n)=φ(pq)=(p-1)(q-1)

Using all this we now have a quick way to solve this problem,

  1. do a double nested loop with variables x, y, going through all primes near 3126 (I went up to 10,000)

  2. See if x*y is a permutation of (x-1)(y-1)

    • If it is see if it less than your current minimum

Originally I solved this without point 3 and it took ~300sec now it takes about ~0.5 sec

I used my Prime Generator function for this

Interactive Code

Enter an integer (yourinput)

Code will output the n such that 1 <= n <= yourinput and the ratio /φ(n) produces a minimum and are permutations of each other