Detailed mathematical approach

Problem Summary

The problem asks for all positive integers \(n\) such that

$\varphi(n)=13!,$

then orders those integers increasingly and asks for the \(150000\)-th entry of that list. This is an inverse-totient problem: instead of evaluating \(\varphi(n)\) for a known \(n\), we must recover every \(n\) whose totient equals the fixed target

$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$

A brute-force scan over \(n\) is not realistic. The workable route is to use the multiplicative structure of \(\varphi\), restrict the possible prime divisors of \(n\), and enumerate only exact factorizations of the target totient.

Mathematical Approach

If

$n=\prod_{k=1}^{m} p_k^{e_k},$

then Euler's product formula gives

$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$

The entire search can therefore be phrased as: find every collection of prime powers whose individual totient contributions multiply exactly to \(13!\).

Factor the target once and exploit it everywhere

The fixed target

$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13$

already tells us that every admissible contribution to \(\varphi(n)\) must divide \(T\). Because the prime factorization of \(T\) is tiny, all divisor-based pruning is cheap. In particular, \(T\) has

$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584$

positive divisors, so the raw candidate space is finite from the start.

Which primes are even allowed?

If a prime \(p\) divides \(n\), then the factor \((p-1)\) appears inside \(\varphi(n)\). Therefore

$p\mid n \quad\Longrightarrow\quad p-1\mid T.$

So every prime divisor of a solution must have the form

$p=d+1\qquad\text{for some divisor }d\text{ of }T,$

with the additional requirement that \(p\) itself be prime. The implementations generate exactly this finite set by enumerating the divisors of \(T\) and testing \(d+1\) for primality.

There is a second, even sharper restriction. If \(p^e\) divides \(n\) with \(e\ge 2\), then

$\varphi(p^e)=(p-1)p^{e-1}\mid T,$

so \(p^{e-1}\mid T\). Hence only primes already dividing \(T\), namely \(2,3,5,7,11,13\), can appear with exponent greater than \(1\). Any larger candidate prime can only appear to the first power.

Prime-power contributions are the real search units

For a fixed admissible prime \(p\), the possible totient contributions are

$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$

Each choice of exponent \(e\) contributes one factor

$c(p,e)=(p-1)p^{e-1}$

to the target \(T\), while the corresponding factor inserted into \(n\) is \(p^e\). The algorithm never guesses arbitrary integers. It only tries these prime-power building blocks, and only when the current remaining totient budget is divisible by the chosen contribution.

An exact recursive decomposition of the inverse-totient set

Let the admissible primes be ordered as

$q_0\lt q_1\lt \cdots \lt q_{m-1}.$

Define \(\mathcal{S}(r,i)\) to be the set of integers built from the primes \(q_i,q_{i+1},\dots,q_{m-1}\) whose totient equals \(r\). Then the recursion used by the implementations is

$\mathcal{S}(1,i)=\{1\},$

and for \(r\gt 1\), define

$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$

Then

$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$

This formula is not just a mathematical reformulation of the code; it is the code's search tree. At each node, the state is the remaining totient factor \(r\), the next usable prime index \(i\), and the partial value of \(n\) accumulated so far.

The key invariant and why duplicates disappear

During the recursion, the following invariant is maintained:

$\varphi(N)\cdot r=T,$

where \(N\) is the partial integer already chosen and \(r\) is the remaining totient budget. Every recursive step replaces \(r\) by \(r/c(p,e)\) and multiplies \(N\) by \(p^e\), so the invariant continues to hold.

The second invariant is ordering: once the search moves past a prime \(q_j\), it never returns to smaller primes. That matters because the prime factorization of \(n\) is unique. Every valid solution has one increasing list of distinct primes and one exponent attached to each of them, so this monotone prime order guarantees that each solution is generated exactly once.

Worked Example: the same recursion on \(\varphi(n)=120\)

The implementations validate the search on the smaller target \(120\), and it is a good example of the mechanics. Here the admissible primes are those with \(p-1\mid 120\), namely

$2,3,5,7,11,13,31,41,61.$

One branch chooses \(p=13\). Since \(\varphi(13)=12\), the remaining budget becomes \(120/12=10\). Then it chooses \(p=11\), whose contribution is \(\varphi(11)=10\). The remainder is now \(1\), so this branch produces

$n=13\cdot 11=143,$

and indeed

$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$

Another branch chooses \(p=31\), using the contribution \(30\), and then \(p=5\), using the contribution \(4\), which gives

$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$

The full problem uses the same search pattern, just with the larger target \(13!\) and a correspondingly larger, but still sharply pruned, recursion tree.

How the Code Works

Generating the admissible primes

The C++, Python, and Java implementations first factor \(13!\), generate all of its divisors, and test each value \(d+1\) for primality. That step produces the complete admissible prime set. The primality testing is deterministic for 64-bit inputs, so no probabilistic uncertainty enters the search.

Enumerating inverse-totient branches

The search state stores three pieces of information: the remaining totient factor, the first prime that may still be used, and the partial integer \(n\). For each candidate prime, the implementation starts with the contribution \(p-1\) and repeatedly multiplies by \(p\) while divisibility still holds. That loop tries exactly the contributions

$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $

that correspond to \(p,p^2,p^3,\dots\). Whenever the remaining totient factor becomes \(1\), the current integer is a complete solution and is recorded.

Because solutions can be much larger than \(13!\), the implementations store candidate values in wide integer types rather than assuming 64-bit signed arithmetic is always sufficient.

Ordering, validation, and parallel work splitting

After enumeration, the solution list is sorted, normalized by removing duplicates defensively, and indexed to extract the \(150000\)-th value. The C++ implementation also includes additional validation layers: it compares the recursive search against brute force for the small target \(120\), checks the known first solution for the main target, recomputes \(\varphi(n)\) from each discovered factorization, and confirms that the multi-threaded and single-threaded searches agree.

When multiple threads are used, the search is split by first-level prime-power choices. Each worker then explores a disjoint subtree of the same recursion, so the mathematical enumeration stays unchanged; only the traversal schedule changes. The Python and Java implementations use the same recursive logic serially.

Complexity Analysis

The preprocessing is small. Factoring \(13!\), generating its \(1584\) divisors, and testing the corresponding values \(d+1\) for primality is negligible compared with the recursive enumeration.

The dominant cost is output-sensitive. If \(B\) is the number of recursive branches visited and \(M\) is the number of solutions found, then the enumeration cost is \(O(B)\), followed by \(O(M\log M)\) for sorting and normalization. There is no simple closed form for \(B\), because it depends on how often divisibility tests succeed, but the search is heavily pruned by the two main restrictions:

$p-1\mid 13! \qquad\text{and}\qquad (p-1)p^{e-1}\mid 13!.$

The recursion depth is modest because every accepted step divides the remaining totient budget by at least \(2\). Memory usage is \(O(M)\) for the stored solutions plus the recursion stack and, in the threaded C++ version, per-worker output buffers.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=248
2. Euler's totient function: Wikipedia - Euler's totient function
3. Inverse totient problem: Wikipedia - Inverse totient
4. Multiplicative function: Wikipedia - Multiplicative function
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test