Detailed mathematical approach

Problem Summary

We seek the integer \(n\) with \(1 \lt n \lt 10^7\) such that \(\varphi(n)\) is a digit permutation of \(n\) and the quotient \(n/\varphi(n)\) is as small as possible. Here \(\varphi(n)\) counts the integers \(1 \le k \le n\) that are coprime to \(n\).

The C++, Python, and Java implementations do not rely on a narrow guess such as "the answer must be semiprime". Instead they compute \(\varphi(n)\) exactly for every \(n\) below the limit, test the digit-permutation condition exactly, and keep the candidate with the smallest ratio.

Mathematical Approach

The key mathematics is the factor formula for Euler's totient function and the observation that it can be turned into a sieve. Once every totient value is available, Problem 70 becomes a direct scan over all \(n \lt 10^7\).

The Totient Product Formula

If the distinct prime divisors of \(n\) are \(p_1,\dots,p_r\), then

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$

This comes from counting the integers in \(\{1,2,\dots,n\}\) that are not divisible by any prime factor of \(n\). Each factor \((1-1/p)\) removes the fraction ruled out by the prime \(p\), and only distinct prime divisors matter.

Equivalently, if \(n=p_1^{a_1}\cdots p_r^{a_r}\), then

$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$

Turning the Formula into a Sieve

Initialize an array with \(\phi(m)=m\) for every \(m\). When a prime \(p\) is encountered, every multiple \(j\) of \(p\) must receive the factor \((1-1/p)\), so the update is

$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$

The key invariant is that after all primes up to \(P\) have been processed,

$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$

Once the last prime divisor of \(j\) has been handled, this becomes exactly \(\varphi(j)\). The update is also an integer step: when the factor for \(p\) is applied, the current value still contains an unremoved factor of \(p\), so \(\phi(j)/p\) is integral at that moment.

The prime test inside the sieve is just as simple. If \(\phi(i)=i\) when the loop reaches \(i\), then no smaller prime has touched it, so \(i\) is prime. Every composite number would already have been reduced by its smallest prime divisor.

The Permutation Condition is a Digit-Multiset Test

The problem asks whether \(n\) and \(\varphi(n)\) use exactly the same decimal digits with the same multiplicities. That is a multiset condition, not an arithmetic identity.

One way to test it is to sort both decimal strings and compare the results. Another is to count how many times each digit \(0,1,\dots,9\) appears and compare the two count vectors. The implementations use both styles: sorting in Python and Java, and a digit-frequency count in C++. Different mechanics, same mathematical test.

Comparing Ratios Exactly

Once a candidate passes the digit test, we must decide whether its ratio is better than the best ratio seen so far. For positive quantities,

$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$

So the ratio comparison can be done by cross-multiplication instead of repeated division. This keeps the ordering exact. The C++ and Python implementations use this integer comparison directly, while the Java implementation evaluates the quotient numerically.

Worked Example: \(n=21\)

This small example mirrors the full method. Start with \(\phi(21)=21\). The prime divisors of 21 are 3 and 7, so the sieve performs

$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$

Hence \(\varphi(21)=12\), which matches the product formula

$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$

The digits of 21 and 12 are the same multiset \(\{1,2\}\), so 21 is a valid candidate. On the restricted range \(n \lt 100\), it is the best one, which makes it a convenient sanity check for the sieve and the ratio comparison. A larger sample from the problem statement is \(87109\), whose totient is \(79180\); the same digit-multiset test accepts that pair as well.

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase structure: first build every totient value below the limit with a sieve, then sweep once through the completed table looking for valid permutations and the minimum ratio.

Phase 1: Build the Totient Table

An array of length \(10^7\) is filled with its own indices. The main loop scans upward from 2. Whenever an entry is still equal to its index, that number is prime, so every multiple of it is updated by the rule \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\). After this phase, the array holds \(\varphi(n)\) for every \(n\) in the search range.

Phase 2: Test the Candidates

The second loop visits each \(n\ge 2\), retrieves its precomputed totient, and checks whether the decimal digits match as a multiset. The C++ implementation uses a 10-entry digit counter, while the Python and Java implementations sort the decimal representations before comparing them.

Phase 3: Maintain the Best Ratio

Whenever a valid permutation is found, the implementation compares its ratio against the current best and updates the stored answer if the new ratio is smaller. Because all totient values are already known, this final phase is a simple linear scan with no recursion, no backtracking, and no number-theoretic guesswork beyond the sieve itself.

Complexity Analysis

Let \(N=10^7\). The totient sieve has the same harmonic-over-primes behavior as other prime sieves and runs in \(O(N\log\log N)\) time. The final scan is \(O(N)\) candidates, with a digit test that is constant-time in practice because numbers below \(10^7\) have at most seven decimal digits. Written asymptotically, that test is \(O(d)\) with digit counts or \(O(d\log d)\) with sorting, where \(d\le 7\).

The memory usage is \(O(N)\) for the totient table. That linear table is the dominant space cost in all three languages, and it is exactly what allows the search to stay exhaustive while still remaining fast enough for the stated limit.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=70
2. Euler's totient function: Wikipedia - Euler's totient function
3. Multiplicative functions: Wikipedia - Multiplicative function
4. Sieve methods: Wikipedia - Sieve of Eratosthenes