Project Euler

Problem 500!!!

The number of divisors of 120 is 16. In fact, 120 is the smallest number having 16 divisors. Find the smallest number with 2^500500 divisors. Give your answer modulo 500500507.

Source sync Apr 19, 2026

Problem #0500

Level Level 07

Solved By 4,661

Languages C++, Python

Answer 35407281

Length 291 words

modular_arithmeticnumber_theorylinear_algebra

The number of divisors of $120$ is $16$.

In fact $120$ is the smallest number having $16$ divisors.

Find the smallest number with $2^{500500}$ divisors.

Give your answer modulo $500500507$.

Problem 500: Problem 500!!!

Mathematical Analysis

Divisor Count Formula

For a number $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ , the number of divisors is:

\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)

We need $\tau(n) = 2^{500500}$ , which means each factor $(a_i + 1)$ must be a power of 2. So each exponent $a_i$ must be of the form $2^j - 1$ for some $j \geq 1$ .

Greedy Strategy

To minimize $n$ , we assign larger exponents to smaller primes. Each “doubling step” either:

Introduces a new prime $p$ with exponent 1 (multiplying $n$ by $p$ ), contributing one factor of 2 to $\tau(n)$ .
Doubles the exponent of an existing prime $p^{2^j - 1}$ to $p^{2^{j+1} - 1}$ (multiplying $n$ by $p^{2^j}$ ), contributing one additional factor of 2 to $\tau(n)$ .

We need exactly 500500 such doubling steps. At each step, we greedily pick the option that multiplies $n$ by the smallest value.

Priority Queue Approach

We maintain a min-heap of candidate values:

Initially, all primes are candidates with value $p$ (adding prime $p$ with exponent 1).
When we pick prime $p$ at level $j$ (meaning $p^{2^j}$ ), we push $p^{2^{j+1}}$ as the next candidate for that prime.

We perform 500500 iterations, always picking the smallest candidate.

Editorial

We generate primes up to ~7500000 (about 500500 primes needed). We then initialize a min-heap with all these primes. Finally, return the answer.

Pseudocode

Generate primes up to ~7500000 (about 500500 primes needed)
Initialize a min-heap with all these primes
For i = 1 to 500500:
Return the answer

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

Time: $O(N \log N)$ where $N = 500500$ , due to heap operations.
Space: $O(N)$ for the heap and prime sieve.

Answer

\boxed{35407281}

C++ project_euler/problem_500/solution.cpp

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 500500507;
const int TARGET = 500500;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    // Sieve primes up to ~7.6 million (need about 500500 primes)
    const int LIMIT = 7800000;
    vector<bool> is_prime(LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= LIMIT; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    for (int i = 2; i <= LIMIT; i++) {
        if (is_prime[i]) primes.push_back(i);
    }

    // Min-heap: (value, base_prime)
    // We store log values for comparison, actual modular product separately
    // Actually, we can use double for comparison and track modular arithmetic
    // Better: use a priority queue of (log_value, prime, current_power_of_two)

    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;

    int prime_idx = 0;
    // Push first prime
    pq.push({log((double)primes[0]), 0});
    prime_idx = 1;

    long long answer = 1;

    for (int i = 0; i < TARGET; i++) {
        // Ensure we have enough primes in the queue
        while (prime_idx < (int)primes.size() &&
               (pq.empty() || log((double)primes[prime_idx]) <= pq.top().first + 1e-9 || prime_idx <= i + 1)) {
            pq.push({log((double)primes[prime_idx]), prime_idx});
            prime_idx++;
        }

        auto [log_val, idx] = pq.top();
        pq.pop();

        // Multiply answer by primes[idx]^(2^j) mod MOD
        // The log_val encodes the actual value; the modular multiplication:
        // We need to compute primes[idx]^(round(exp(log_val)/1)) but that's imprecise.
        // Better approach: store the actual prime and exponent level

        // Actually, let's redo this properly
        // Store (log_value, prime_index, level) where the actual multiplier is prime^(2^level)
        // and log_value = 2^level * log(prime)

        // For now, compute modular value from prime and level
        // We need to track level. Let me restart with a cleaner approach.
        break;
    }

    // Clean approach: store (log_value, prime, level)
    // where multiplier = prime^(2^level), log_value = 2^level * log(prime)

    struct Entry {
        double log_val;
        int prime_idx;
        int level;
        bool operator>(const Entry& o) const { return log_val > o.log_val; }
    };

    priority_queue<Entry, vector<Entry>, greater<Entry>> pq2;

    for (int i = 0; i < min((int)primes.size(), TARGET + 100); i++) {
        pq2.push({log((double)primes[i]), i, 0});
    }

    answer = 1;
    for (int i = 0; i < TARGET; i++) {
        Entry e = pq2.top();
        pq2.pop();

        // Multiplier is primes[e.prime_idx]^(2^e.level)
        long long mult = power(primes[e.prime_idx], 1LL << e.level, MOD);
        answer = answer * mult % MOD;

        // Push next level
        pq2.push({e.log_val * 2, e.prime_idx, e.level + 1});
    }

    cout << answer << endl;

    return 0;
}

Python project_euler/problem_500/solution.py

import heapq
import math

def solve():
    MOD = 500500507
    TARGET = 500500

    # Sieve primes
    LIMIT = 7800000
    is_prime = bytearray(b'\x01') * (LIMIT + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(LIMIT**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))

    primes = [i for i in range(2, LIMIT + 1) if is_prime[i]]

    # Min-heap: (log_value, prime_index, level)
    # multiplier = prime^(2^level), log_value = 2^level * log(prime)
    heap = []
    for i in range(min(len(primes), TARGET + 100)):
        heapq.heappush(heap, (math.log(primes[i]), i, 0))

    answer = 1
    for _ in range(TARGET):
        log_val, idx, level = heapq.heappop(heap)

        # Multiply by primes[idx]^(2^level) mod MOD
        mult = pow(primes[idx], 1 << level, MOD)
        answer = answer * mult % MOD

        # Push next level
        heapq.heappush(heap, (log_val * 2, idx, level + 1))

    print(answer)

solve()