Totient Permutation¶

SageMath's implementation of $\phi(n)$ is fast enough that you could brute force this if you wanted, but if we're clever, we can solve more quickly.

We'll write a simple function for determining if two numbers are digit permutations of each other.

In [1]:
def is_permutation_pair(a, b):
    s, t = str(a), str(b)
    return sorted(s) == sorted(t)

As in problem 69, $$\phi(n) = n\prod_{p | n} \left(1 - \frac{1}{p}\right)$$

We can calculate the totients of the numbers up to $10^7$ using a very similar approach to the sieve of Eratosthenes for generating prime numbers (see problem 10). Iterating over values of $n$, if totients[n] == n - 1, then $n$ is prime, and we'll update all its multiples using the above formula.

In [2]:
def totient_range(limit):
    totients = [n - 1 for n in range(0, limit)]
    totients[0] = 0
    totients[1] = 1
    
    for n in range(0, limit):
        yield totients[n]
        if n == 0 or n == 1 or totients[n] != n - 1:
            continue

        for k in range(2 * n, limit, n):
            totients[k] -= totients[k] // n

$n-1$ can't be a permutation of $n$, so our solution won't be prime. If $n$ is composite, then we'll check if $n/\phi(n)$ is small and if $\phi(n)$ is a permutation of $n$, keeping track of the best answer so far.

In [3]:
limit = 10^7

answer = None
ratio = float('inf')

for (n, totient) in enumerate(totient_range(limit)):
    if n == 0 or n == 1 or totient == n - 1:
        continue
        
    r = n / totient
    if r < ratio and is_permutation_pair(n, totient):
        ratio = r
        answer = n
In [4]:
answer
Out[4]:
8319823

Note: lots of people in the problem thread make the assumption that the answer must be a semiprime. However, Steendor points out that for certain upper bounds, this assumption does not hold. For instance, $2817 = 3^2 \times 313$ and $\phi(2817) = 1872$, and 2817/1872 is the lowest ratio until 2991. 2817 may be an exception rather than the norm (all the other numbers in A102018 up to $10^8$ are semiprimes); nevertheless, this solution avoids making the assumption.

Relevant sequences¶

  • All numbers $n$ such that $\phi(n)$ is a digit permutation: A115921
  • Subsequence of A115921 such that $n/\phi(n)$ is a record low: A102018

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.