# Project Euler Solution 70: Totient permutation

Project Euler Problem 70: Totient permutation continues with the totient function.

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.

This feels like a direct continuation of Problem 69: Totient maximum. The stark difference is that we look for a *minimum* here whereas in Problem 69 we have looked for a *maximum* of the expression $n/\phi(n)$.

In the previous post we have learned that the ratio $n/\phi(n)$ can be written like this: $$ \frac{n}{\phi(n)} = \prod_i \frac{p_i}{p_i - 1} \,. $$

We can see that each factor is greater than one. If we are to maximize this, we need to take as many small prime factors as we can. If we take a look at the numbers for $n < 1\,000$ and create a table sorted by maximal value of $n/\phi(n)$, we get these numbers consisting of small primes:

n | Prime factors | $\phi(n)$ | $n/\phi(n)$ |
---|---|---|---|

840 | $2^{3} \cdot 3 \cdot 5 \cdot 7$ | 192 | 4.3750 |

630 | $2 \cdot 3^{2} \cdot 5 \cdot 7$ | 144 | 4.3750 |

420 | $2^{2} \cdot 3 \cdot 5 \cdot 7$ | 96 | 4.3750 |

210 | $2 \cdot 3 \cdot 5 \cdot 7$ | 48 | 4.3750 |

990 | $2 \cdot 3^{2} \cdot 5 \cdot 11$ | 240 | 4.1250 |

660 | $2^{2} \cdot 3 \cdot 5 \cdot 11$ | 160 | 4.1250 |

330 | $2 \cdot 3 \cdot 5 \cdot 11$ | 80 | 4.1250 |

780 | $2^{2} \cdot 3 \cdot 5 \cdot 13$ | 192 | 4.0625 |

390 | $2 \cdot 3 \cdot 5 \cdot 13$ | 96 | 4.0625 |

510 | $2 \cdot 3 \cdot 5 \cdot 17$ | 128 | 3.9844 |

570 | $2 \cdot 3 \cdot 5 \cdot 19$ | 144 | 3.9583 |

690 | $2 \cdot 3 \cdot 5 \cdot 23$ | 176 | 3.9205 |

870 | $2 \cdot 3 \cdot 5 \cdot 29$ | 224 | 3.8839 |

930 | $2 \cdot 3 \cdot 5 \cdot 31$ | 240 | 3.8750 |

924 | $2^{2} \cdot 3 \cdot 7 \cdot 11$ | 240 | 3.8500 |

462 | $2 \cdot 3 \cdot 7 \cdot 11$ | 120 | 3.8500 |

546 | $2 \cdot 3 \cdot 7 \cdot 13$ | 144 | 3.7917 |

We are interested in the other thing now. We want to have the fewest factors and with the largest primes. Sorting the table the other way around shows that indeed the largest primes have the smallest $n/\phi(n)$:

n | Prime factors | $\phi(n)$ | $n/\phi(n)$ |
---|---|---|---|

997 | $997$ | 996 | 1.0010 |

991 | $991$ | 990 | 1.0010 |

983 | $983$ | 982 | 1.0010 |

977 | $977$ | 976 | 1.0010 |

971 | $971$ | 970 | 1.0010 |

967 | $967$ | 966 | 1.0010 |

953 | $953$ | 952 | 1.0011 |

947 | $947$ | 946 | 1.0011 |

941 | $941$ | 940 | 1.0011 |

937 | $937$ | 936 | 1.0011 |

929 | $929$ | 928 | 1.0011 |

919 | $919$ | 918 | 1.0011 |

911 | $911$ | 910 | 1.0011 |

907 | $907$ | 906 | 1.0011 |

887 | $887$ | 886 | 1.0011 |

The problem with primes is that their totient is just one less than the prime, namely $\phi(p) = p - 1$. But that means that the $p$ and $\phi(p)$ cannot be digit permutations of each other. We need to have a product of at least two primes to get somesomething of interest.

We can filter the table to only include numbers such that the number and its totient are digit permutations. We also increase the ceiling to 100,000 such that we get more interesting results. These are the minimum numbers that we get:

n | Prime factors | $\phi(n)$ | $n/\phi(n)$ |
---|---|---|---|

75841 | $149 \cdot 509$ | 75184 | 1.0087 |

84283 | $89 \cdot 947$ | 83248 | 1.0124 |

94813 | $59 \cdot 1607$ | 93148 | 1.0179 |

69271 | $53 \cdot 1307$ | 67912 | 1.0200 |

45421 | $53 \cdot 857$ | 44512 | 1.0204 |

20617 | $53 \cdot 389$ | 20176 | 1.0219 |

22471 | $23 \cdot 977$ | 21472 | 1.0465 |

35683 | $17 \cdot 2099$ | 33568 | 1.0630 |

87109 | $11 \cdot 7919$ | 79180 | 1.1001 |

86965 | $5 \cdot 17393$ | 69568 | 1.2501 |

49435 | $5 \cdot 9887$ | 39544 | 1.2501 |

44305 | $5 \cdot 8861$ | 35440 | 1.2501 |

4435 | $5 \cdot 887$ | 3544 | 1.2514 |

67045 | $5 \cdot 11 \cdot 23 \cdot 53$ | 45760 | 1.4651 |

We can see that we need at least two factors. And the one with minimal $n/\phi(n)$ has two rather large prime factors. The other ones still have pretty large prime factors. When we get down to the point where we have 5 as a prime factor, the ratio $n/\phi(n)$ is already pretty large with above 1.25.

It seems likely that the desired answer $n$ is the product of two prime numbers. It could be that it is a product of three primes, but let us persue the hypothesis that it is a product of two largish primes.

We can then look at all products of primes $p_1 p_2$ where $p_i < 10\,000$. We obtain the following top 15 entries:

n | Prime factors | $\phi(n)$ | $n/\phi(n)$ |
---|---|---|---|

75841 | $149 \cdot 509$ | 75184 | 1.0087 |

84283 | $89 \cdot 947$ | 83248 | 1.0124 |

94813 | $59 \cdot 1607$ | 93148 | 1.0179 |

69271 | $53 \cdot 1307$ | 67912 | 1.0200 |

45421 | $53 \cdot 857$ | 44512 | 1.0204 |

20617 | $53 \cdot 389$ | 20176 | 1.0219 |

22471 | $23 \cdot 977$ | 21472 | 1.0465 |

35683 | $17 \cdot 2099$ | 33568 | 1.0630 |

87109 | $11 \cdot 7919$ | 79180 | 1.1001 |

86965 | $5 \cdot 17393$ | 69568 | 1.2501 |

49435 | $5 \cdot 9887$ | 39544 | 1.2501 |

44305 | $5 \cdot 8861$ | 35440 | 1.2501 |

4435 | $5 \cdot 887$ | 3544 | 1.2514 |

56937 | $3 \cdot 18979$ | 37956 | 1.5001 |

53967 | $3 \cdot 17989$ | 35976 | 1.5001 |

Unsurisingly these are the same numbers that we have found before. The problem is that with a ceiling of 10,000, this already takes 2.8 s to compute. The search scales roughly quadratically with the ceiling. So going up to the required 10,000,000 means another factor 1,000 more prime numbers and therefore 1,000,000 more compute time. It would take several months to finish, so this cannot be it.

We can save a bit of time by using that we already know the prime factors. Then we don't have to factorize the number again to compute the totient function. This brings the time down to 47 ms for this table.

There is another insight that we can use. Although the ceiling is 10,000,000, we don't need prime numbers that high. Since we want both prime numbers of the same order of magnitude, it is sufficient to only look at primes that are up to 10,000. This means that we just need to add a factor of 10 to the primes and this increases computation cost only a bit.

We then get this table:

n | Prime factors | $\phi(n)$ | $n/\phi(n)$ |
---|---|---|---|

8319823 | $2339 \cdot 3557$ | 8313928 | 1.000709 |

8357821 | $2273 \cdot 3677$ | 8351872 | 1.000712 |

8316907 | $2273 \cdot 3659$ | 8310976 | 1.000714 |

7507321 | $2243 \cdot 3347$ | 7501732 | 1.000745 |

7357291 | $2297 \cdot 3203$ | 7351792 | 1.000748 |

7026037 | $2609 \cdot 2693$ | 7020736 | 1.000755 |

7276201 | $2063 \cdot 3527$ | 7270612 | 1.000769 |

6636841 | $2459 \cdot 2699$ | 6631684 | 1.000778 |

6640351 | $2129 \cdot 3119$ | 6635104 | 1.000791 |

9848203 | $1559 \cdot 6317$ | 9840328 | 1.000800 |

8280673 | $1583 \cdot 5231$ | 8273860 | 1.000823 |

6018163 | $2027 \cdot 2969$ | 6013168 | 1.000831 |

9179251 | $1487 \cdot 6173$ | 9171592 | 1.000835 |

5886817 | $2003 \cdot 2939$ | 5881876 | 1.000840 |

6749683 | $1667 \cdot 4049$ | 6743968 | 1.000847 |

And it turns out that the top entry is already the solution that we were looking for. The number consists of two large primes.

So what is left in the code is just a function that checks for permutations using `sort_digits`

from Solution 62: Cubic permutations

def are_permutations(left: int, right: int) -> bool: return sort_digits(left) == sort_digits(right)

And then the main function goes through the primes which are generated with the prime sieve from Solution 7: 10001st prime:

def solution() -> int: primes = prime_sieve(10**5) values = [] for p1 in primes: for p2 in primes: if p1 == p2: break number = p1 * p2 if number > 10**7: break t = (p1 - 1) * (p2 - 1) if are_permutations(t, number): values.append((number / t, number)) return min(values)[1]

It took 754 ms to compute, which is fine.