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