Detailed mathematical approach

Problem Summary

Write a positive integer \(n\gt 1\) in the form

$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$

where the primes are listed in increasing order. Problem 578 asks for the counting function

$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$

with \(1\) also counted. The difficulty is that \(N\) is enormous, so the solution cannot test each integer separately. Instead, it counts valid factorizations by their exponent pattern and then counts how many prime choices realize each pattern.

Mathematical Approach

The implementations split the problem into two layers: first enumerate every feasible nonincreasing exponent pattern, then count the prime tuples that fit that pattern under the bound \(N\).

Step 1: Separate Numbers by Exponent Signature

Every valid integer \(n\gt 1\) has a unique signature

$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$

For a fixed signature define

$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$

Then

$C(N)=1+\sum_{\lambda} A_\lambda(N),$

where the \(+1\) accounts for \(n=1\). A signature is feasible only if even its smallest possible realization fits:

$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$

This observation is the foundation for the signature-generation recursion.

Step 2: Count Prime Choices for One Fixed Signature

Let \(p_1,p_2,\dots\) denote the prime numbers. Suppose we have already committed to primes up through \(p_i\), so the next chosen prime must be larger than \(p_i\). For a remaining exponent list \((f_1,\dots,f_r)\) and a remaining limit \(L\), define

$R(f_1,\dots,f_r;L,i)$

to be the number of strictly increasing prime choices \(q_1\lt \cdots \lt q_r\), all greater than \(p_i\), such that

$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$

The recursive relation is

$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$

The desired count for a full signature is simply

$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$

Step 3: Collapse Terminal Branches with \(\pi(x)\)

When only one exponent \(e\) remains, the recursion reduces to counting primes:

$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$

The reason is simple: any prime \(q\) larger than the first \(i\) primes is valid exactly when \(q^e\le L\).

When two exponents \(e\ge f\) remain, we obtain

$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$

This is much faster than descending one level deeper for every pair. The C++ implementation also gives special treatment to common exponents \(1,2,4,8\), because the corresponding bounds can be obtained by exact integer roots.

Step 4: Prune by the Minimal Possible Continuation

For long signatures, most branches are impossible. If we are considering the next prime \(p_j\) for the remaining exponents \((f_1,\dots,f_r)\), then even the smallest possible continuation would use consecutive larger primes:

$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$

If this minimal product already exceeds \(L\), then no later choice of \(p_j\) can work, because later primes are only larger. So the search can stop immediately at that point instead of exploring dead branches.

Step 5: Enumerate All Feasible Signatures Exactly Once

A separate recursion generates the signatures themselves. Start with an exponent \(e_1\ge 1\) satisfying \(2^{e_1}\le N\). For the next position choose \(e_2\) with

$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$

Then continue with \(5,7,11,\dots\) as the smallest possible future primes. Every time a prefix \((e_1,\dots,e_t)\) is feasible with these minimal primes, that prefix represents a genuine signature, so its contribution \(A_{(e_1,\dots,e_t)}(N)\) is added immediately. Extending the prefix by a new exponent \(e_{t+1}\le e_t\) guarantees that each nonincreasing signature appears once and only once.

Worked Example: Signature \((2,1)\) for \(N=100\)

Here we count numbers of the form \(p^2q\) with \(p\lt q\) and \(p^2q\le 100\). The formula becomes

$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$

Now evaluate each possible first prime:

$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$

So \(A_{(2,1)}(100)=11\). The same pruning idea also shows immediately that the longer signature \((2,2,1)\) is impossible at \(N=100\), because its minimal realization would be

$2^2\cdot 3^2\cdot 5=180>100.$

When all feasible signatures are summed, the total is \(C(100)=94\), which matches the implementation's checkpoint.

How the Code Works

The C++ implementation begins by precomputing a compressed prime-count structure. It stores enough information to answer \(\pi(x)\) quickly both for small values of \(x\) and for quotient values of the form \(\lfloor N/v\rfloor\). It also precomputes prime powers \(p^e\le N\) for the primes that can matter in recursive branches.

After that, one recursive routine generates every feasible nonincreasing exponent signature, using the minimal primes \(2,3,5,\dots\) only as a feasibility test. Another recursive routine counts prime tuples for the current signature. Whenever only one or two exponents remain, the search switches to direct prime-count formulas instead of recursing blindly. Independent top-level branches, distinguished by the first exponent, are processed in parallel and then added together.

The Python and Java implementations do not reimplement the mathematics separately. They invoke the same compiled computation and extract the final numeric answer, so all three language versions use the same counting method.

Complexity Analysis

There is no clean closed form depending only on \(N\), because the search cost is governed by how many exponent signatures survive the feasibility tests and how many prime branches survive pruning. The prime-count preprocessing stores \(O(\sqrt{N})\) distinct arguments and uses \(O(\sqrt{N})\) memory; its arithmetic cost is close to \(O(\sqrt{N}\log\log N)\).

After preprocessing, let \(B(N)\) denote the total number of recursive states that remain after pruning. Then the overall running time is roughly

$O\!\left(\sqrt{N}\log\log N + B(N)\right),$

with terminal branches answered by fast \(\pi(x)\) queries rather than full subtree expansion. In practice, this is dramatically smaller than enumerating all integers up to \(N\), which is why the method is fast enough for the Project Euler bound.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=578
2. Prime-counting function: Wikipedia - Prime-counting function
3. Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic
4. Integer partition: Wikipedia - Partition (number theory)
5. Prime power: Wikipedia - Prime power