Solution

Answer: 35407281

Let $d(n)$ denote the number of positive divisors of $n$.

The problem asks for the smallest integer $N$ such that

$$d(N)=2^{500500}.$$

We must compute $N \bmod 500500507$.

1. Mathematical analysis

$$N=\prod_{i=1}^k p_i^{a_i},$$

then the divisor-count formula gives

$$d(N)=\prod_{i=1}^k (a_i+1).$$

We want this to equal a pure power of two:

$$\prod (a_i+1)=2^{500500}.$$

Therefore every factor $a_i+1$ must itself be a power of two:

$$a_i = 2^{b_i}-1.$$

So the exponents must be of the form

$$1,3,7,15,31,\dots$$

and

$$\sum b_i = 500500.$$

Thus

$$N=\prod p_i^{,2^{b_i}-1}.$$

The question becomes:

How do we distribute the “budget” $500500$ among primes to minimize $N$?

Key greedy insight

Suppose we currently use exponent block $b$ on a prime $p$.

Increasing $b$ by $1$ changes exponent from

$$2^b-1 \quad\to\quad 2^{b+1}-1.$$

So the exponent increases by exactly $2^b$.

That multiplies $N$ by

$$p^{2^b}.$$

Hence every additional unit of divisor-exponent budget costs a multiplicative factor:

$$p^{2^b}.$$

To minimize $N$, at every step we should choose the smallest available multiplier.

Reformulation

Initially, every prime can contribute one factor of $2$ to the divisor count by appearing with exponent $1$.

That costs multiplying by $p$.

If we later upgrade exponent

$$1 \to 3,$$

we multiply by $p^2$.

Then

$$3 \to 7$$

costs multiplying by $p^4$, etc.

So the candidate costs are:

$$2,3,5,7,11,\dots$$

(first appearances)

then

$$2^2,3^2,5^2,\dots$$

then

$$2^4,3^4,\dots$$

and so on.

We must select exactly $500500$ such costs, always taking the smallest available next option.

This is a classic priority-queue / heap process.

Why the greedy strategy is correct

Suppose two choices are available:

multiply by $a$,
multiply by $b$,

with $a<b$.

Since all future multipliers are independent and positive, choosing $a$ first always yields a smaller total product than choosing $b$ first.

Thus repeatedly taking the smallest available multiplier is globally optimal.

2. Efficient algorithm

We maintain a min-heap containing the next available multiplier for each prime.

For a prime $p$:

first multiplier is $p$,
after taking $p^{2^k}$, the next multiplier becomes

$$p^{2^{k+1}}=(p^{2^k})^2.$$

So each time we pop value $x$, we push back

$$x^2.$$

But we only need values for heap ordering, not exact gigantic integers.

Still, Python big integers handle this fine because heap size is only about $500500$.

We also maintain the answer modulo $500500507$.

3. Python implementation

import heapq

MOD = 500500507
TARGET = 500500

# ------------------------------------------------------------
# Generate enough primes using a sieve
# ------------------------------------------------------------

# We need roughly the first 500500 primes.
# The 500500th prime is below 8,000,000.
LIMIT = 8000000

sieve = bytearray(b"\x01") * (LIMIT + 1)
sieve[0:2] = b"\x00\x00"

for i in range(2, int(LIMIT ** 0.5) + 1):
    if sieve[i]:
        step = i
        start = i * i
        sieve[start: LIMIT + 1: step] = b"\x00" * (
            (LIMIT - start) // step + 1
        )

primes = [i for i, is_prime in enumerate(sieve) if is_prime]

# ------------------------------------------------------------
# Greedy heap process
# ------------------------------------------------------------

heap = []

# Initially each prime contributes multiplier p
for p in primes[:TARGET]:
    heapq.heappush(heap, (p, p))

answer = 1

for _ in range(TARGET):
    value, prime = heapq.heappop(heap)

    # Multiply into answer modulo MOD
    answer = (answer * (value % MOD)) % MOD

    # Next upgrade cost for this prime:
    # p^(2^k) -> p^(2^(k+1)) by squaring
    next_value = value * value

    heapq.heappush(heap, (next_value, prime))

print(answer)

4. Code walkthrough

Prime generation

We generate enough primes with the Sieve of Eratosthenes.

LIMIT = 8000000

This safely exceeds the $500500$-th prime.

Heap initialization

heapq.heappush(heap, (p, p))

Each heap entry stores:

current multiplier,
underlying prime.

Initially the multiplier is simply $p$.

Main loop

We repeat exactly $500500$ times because each chosen multiplier contributes one factor of $2$ to the divisor count.

value, prime = heapq.heappop(heap)

Take the smallest available multiplier.

Multiply it into the answer modulo $500500507$.

Then push the next upgrade:

next_value = value * value

because

$$p^{2^k} \mapsto p^{2^{k+1}}.$$

5. Small-example verification

The problem states:

smallest number with $16=2^4$ divisors is $120$.

Let us simulate:

Available multipliers initially:

$$2,3,5,7,\dots$$

Take 4 smallest selections:

$2$
$3$
$2^2=4$
$5$

Product:

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

Exponents become:

$$2^3 \cdot 3^1 \cdot 5^1,$$

whose divisor count is

$$(3+1)(1+1)(1+1)=16.$$

Correct.

6. Final verification

We choose exactly $500500$ multiplicative upgrades, so divisor count is exactly $2^{500500}$.
Greedy choice guarantees minimality.
Modular multiplication keeps computation feasible.
This is the standard optimal construction for the problem.

Running the algorithm gives:

$$35407281$$

Answer: 35407281

Project Euler Problem 500