Detailed mathematical approach

Problem Summary

We want the smallest positive integer \(n\) whose number of divisors is exactly \(2^K\), where \(K=500{,}500\), and we only need the final value modulo \(M=500{,}500{,}507\). The minimum itself is astronomically large, so the solution never tries to build \(n\) explicitly. Instead, it minimizes the prime-power decisions that define \(n\).

Mathematical Approach

Write the prime factorization of \(n\) as

$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$

The divisor formula gives

$d(n)=\prod_{i\ge 1}(a_i+1).$

So the entire problem is controlled by how the factors \(a_i+1\) multiply to \(2^K\).

Step 1: Turn the divisor condition into powers of two

Because \(2^K\) has no odd prime factor, every factor \(a_i+1\) in the product must itself be a power of two. Hence there are integers \(b_i\ge 0\) such that

$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$

and the divisor requirement becomes

$\sum_{i\ge 1} b_i=K.$

So we may think of the problem as distributing \(K\) identical units among the primes. If prime \(p_i\) receives \(b_i\) units, its final exponent is \(2^{b_i}-1\).

Step 2: One extra unit creates one multiplicative cost

Suppose a prime currently has exponent \(2^t-1\). Giving that same prime one more unit changes the exponent to

$2^{t+1}-1=(2^t-1)+2^t,$

so \(n\) is multiplied by

$p^{2^t}.$

Thus each prime contributes an increasing sequence of possible elementary multipliers:

$p,\ p^2,\ p^4,\ p^8,\ \dots.$

If we take the first \(r\) terms from that sequence, their product is

$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$

which matches the exponent pattern required by the divisor formula.

Step 3: The optimum is the product of the \(K\) smallest admissible multipliers

Combine all prime sequences into one infinite multiset

$\mathcal{U}=\left\{p^{2^t}: p \text{ prime},\ t\ge 0\right\}.$

Any valid solution corresponds to choosing exactly \(K\) elements from \(\mathcal{U}\), with one important restriction: within the sequence for each fixed prime, we must choose a prefix. The final integer \(n\) is exactly the product of the chosen elements.

Now note that every sequence \(p,p^2,p^4,\dots\) is strictly increasing. Therefore, if some term \(p^{2^t}\) is among the first \(K\) smallest elements of \(\mathcal{U}\), then all earlier terms in that same sequence are even smaller and must also be among the first \(K\) smallest. So the first \(K\) smallest elements automatically satisfy the prefix rule.

That means the minimum possible \(n\) is simply the product of the \(K\) smallest elements of \(\mathcal{U}\). Replacing any chosen multiplier by a larger available one can only increase the final product.

Step 4: Why only the first \(K\) primes matter

Every distinct prime used in \(n\) consumes at least one unit, so an optimal solution can involve at most \(K\) different primes. If a larger prime were used while a smaller prime remained unused, replacing the larger prime by the smaller one would keep the divisor count unchanged and strictly decrease \(n\).

Equivalently, if \(p_{K+1}\) is the \((K+1)\)-st prime, then its first possible multiplier is \(p_{K+1}\), but there are already \(K\) smaller initial multipliers

$p_1,p_2,\dots,p_K.$

So no term from primes beyond \(p_K\) can belong to the first \(K\) chosen multipliers.

Step 5: Enumerate the multipliers with a min-heap

Start with the first \(K\) primes in a min-heap, each represented by its current offer. Repeatedly remove the smallest current offer \(q\), multiply the running answer by \(q\), and insert the next offer from the same prime, namely \(q^2\). After exactly \(K\) extractions, we have multiplied together the \(K\) smallest admissible multipliers.

If the current offer is \(q=p^{2^t}\), then the next offer from that prime is indeed

$p^{2^{t+1}}=q^2.$

The implementations compare offers by \(\log q\) rather than by the enormous integer \(q\) itself, because

$q_1\lt q_2 \iff \log q_1\lt \log q_2.$

At the same time, they keep the same offer reduced modulo \(M\), so the final result can be accumulated mod \(M\) without ever materializing the full minimum.

Worked Example: \(K=4\)

For \(K=4\), we need exactly \(2^4=16\) divisors. The initial heap offers are \(2,3,5,7\).

Greedy selection proceeds as follows:

$\begin{aligned} \text{pick }2 &\Rightarrow \text{product }=2,\ \text{next offer }=4,\\ \text{pick }3 &\Rightarrow \text{product }=6,\ \text{next offer }=9,\\ \text{pick }4 &\Rightarrow \text{product }=24,\ \text{next offer }=16,\\ \text{pick }5 &\Rightarrow \text{product }=120,\ \text{next offer }=25. \end{aligned}$

So the chosen multipliers are \(2,3,4,5\), and hence

$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$

Its divisor count is

$d(120)=(3+1)(1+1)(1+1)=16=2^4,$

which matches the small checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. First they generate the first \(K\) primes using a sieve together with a standard upper-bound estimate for the \(K\)-th prime. If the first estimate is too small, the bound is enlarged and the sieve is repeated.

They then build a min-heap whose entries store two views of the same current offer \(q\): a logarithmic key \(\log q\) for ordering, and the reduced residue \(q\bmod M\) for modular arithmetic. Initially the heap contains one offer for each of the first \(K\) primes.

Each of the \(K\) iterations removes the smallest offer, multiplies the running answer by its residue modulo \(M\), squares that residue modulo \(M\), doubles the logarithmic key, and pushes the updated offer back into the heap. This exactly enumerates the \(K\) smallest admissible multipliers in order. The C++ implementation also includes tiny checkpoint tests on small divisor powers to validate the greedy construction.

Complexity Analysis

Let \(P_K\) be the \(K\)-th prime. Generating the first \(K\) primes with an ordinary sieve up to \(P_K\) costs \(O(P_K\log\log P_K)\) time and \(O(P_K)\) memory. The heap contains \(K\) entries, and the \(K\) pop-push iterations cost \(O(K\log K)\) time and \(O(K)\) extra memory.

Since \(P_K=\Theta(K\log K)\), the total running time is roughly \(O(K\log K\log\log K)\), and the total memory usage is \(O(P_K+K)\). For the fixed value \(K=500{,}500\), this is comfortably practical.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=500
2. Divisor function: Wikipedia — Divisor function
3. Prime number theorem: Wikipedia — Prime number theorem
4. Priority queue: Wikipedia — Priority queue
5. Greedy algorithm: Wikipedia — Greedy algorithm