Project Euler

Factorials Divisible by a Huge Integer

Let N(i) be the smallest integer n such that n! is divisible by (i!)^1234567890. Define S(u) = sum_(i=10)^u N(i). Given: S(1000) = 614538266565663. Find S(1000000) mod 10^18.

Source sync Apr 19, 2026

Problem #0320

Level Level 15

Solved By 1,057

Languages C++, Python

Answer 278157919195482643

Length 286 words

number_theorymodular_arithmeticsearch

Let $N(i)$ be the smallest integer $n$ such that $n!$ is divisible by $(i!)^{1234567890}$

Let $S(u)=\sum N(i)$ for $10 \le i \le u$.

$S(1000)=614538266565663$.

Find $S(1\,000\,000) \bmod 10^{18}$.

Problem 320: Factorials Divisible by a Huge Integer

Mathematical Analysis

Prime Factorization Approach

For $(i!)^E \mid n!$ (where $E = 1234567890$ ), we need for every prime $p$ :

\nu_p(n!) \ge E \cdot \nu_p(i!)

where $\nu_p(m!)$ is given by Legendre’s formula:

\nu_p(m!) = \sum_{k=1}^{\infty} \left\lfloor \frac{m}{p^k} \right\rfloor

Finding N(i)

For each prime $p \le i$ , define the target:

T_p(i) = E \cdot \nu_p(i!) = E \cdot \sum_{k=1}^{\infty} \left\lfloor \frac{i}{p^k} \right\rfloor

Then find the smallest $n_p$ such that $\nu_p(n_p!) \ge T_p(i)$ using binary search. Since $\nu_p(n!)$ is non-decreasing in $n$ , binary search works directly.

The answer for each $i$ is:

N(i) = \max_{p \text{ prime}, p \le i} n_p(i)

Key Optimization: Incremental Updates

Observation 1: $\nu_p(i!) = \nu_p((i-1)!) + \nu_p(i)$ . So as $i$ increases by 1, $T_p(i)$ changes only for primes $p$ dividing $i$ , and it increases by $E \cdot \nu_p(i)$ .

Observation 2: Since $T_p(i)$ is non-decreasing in $i$ for each $p$ , the corresponding $n_p(i)$ is also non-decreasing. Therefore $N(i) = \max_p n_p(i)$ is non-decreasing.

This means we can maintain a running maximum current_max:

For each $i$ $i$ from 2 to $10^6$ $1 0^{6}$ :
- Factorize $i$ (using smallest-prime-factor sieve, $O(\log i)$ ).
- For each prime factor $p$ $p$ of $i$ $i$ with $\nu_p(i) = v$ $ν_{p} (i) = v$ :
  - Update $T_p \mathrel{+}= E \cdot v$ .
  - Binary search for new $n_p$ (the smallest $n$ with $\nu_p(n!) \ge T_p$ ).
  - Update current_max = max(current_max, n_p).
- If $i \ge 10$ : accumulate $N(i) =$ current_max into the sum.

Binary Search Details

For the binary search on $n_p$ :

Lower bound: $n = 0$
Upper bound: $T_p \cdot p$ (since $\nu_p(n!) \ge n/p$ , we need $n \le T_p \cdot p$ )
Steps: $O(\log(T_p \cdot p)) \approx O(50)$

Total Work

The number of updates across all $i$ is:

\sum_{\text{prime } p \le 10^6} \frac{10^6}{p} \approx 10^6 \cdot \ln\ln(10^6) \approx 3 \times 10^6

Each update involves a binary search with $O(50)$ steps, each step computing Legendre’s formula in $O(\log_p n) \le O(50)$ .

Total: $\approx 7.5 \times 10^9$ operations. In practice, most primes are large (so $\log_p n$ is small), and the actual runtime is a few seconds.

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

Time: $O\!\left(\sum_{p \text{ prime}} \frac{N}{p} \cdot \log^2(E \cdot N)\right) \approx O(N \log\log N \cdot \log^2(EN))$
Space: $O(\pi(N))$ for storing targets and $n_p$ values per prime.

Answer

\boxed{278157919195482643}

C++ project_euler/problem_320/solution.cpp

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

/*
 * Problem 320: Factorials Divisible by a Huge Integer
 *
 * N(i) = smallest n such that (i!)^E | n!, where E = 1234567890.
 * S = sum of N(i) for i = 10 to 1000000, modulo 10^18.
 *
 * For each prime p, the constraint is: v_p(n!) >= E * v_p(i!)
 * where v_p(m!) = sum_{k>=1} floor(m/p^k) (Legendre's formula).
 * N(i) = max over primes p <= i of min_n(p, E * v_p(i!)).
 *
 * Key insight: N(i) is non-decreasing (each n_p(i) is non-decreasing in i),
 * so we can maintain a running max. We track target_p = E * v_p(i!) incrementally
 * and only update when i is divisible by p.
 */

typedef long long i64;
typedef __int128 i128;

const int MAXN = 1000001;
const i64 E = 1234567890LL;
const i64 MOD = 1000000000000000000LL; // 10^18

bool is_prime[MAXN];
int spf[MAXN]; // smallest prime factor

// Legendre's formula: v_p(n!)
i64 legendre(i64 n, i64 p) {
    i64 s = 0;
    i64 pk = p;
    while (pk <= n) {
        s += n / pk;
        if (pk > n / p) break;
        pk *= p;
    }
    return s;
}

// Smallest n such that v_p(n!) >= target
i64 min_n_for_target(i64 p, i64 target) {
    if (target <= 0) return 0;
    i64 lo = 0;
    // Upper bound: v_p(n!) ~ n/(p-1), so n ~ target*(p-1)
    // But need to be safe with overflow
    i128 hi128 = (i128)target * (i128)p;
    i64 hi = (hi128 > (i128)2e18) ? (i64)2e18 : (i64)hi128;

    while (lo < hi) {
        i64 mid = lo + (hi - lo) / 2;
        if (legendre(mid, p) >= target)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

int main() {
    // Sieve
    fill(is_prime, is_prime + MAXN, true);
    is_prime[0] = is_prime[1] = false;
    memset(spf, 0, sizeof(spf));
    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i]) {
            spf[i] = i;
            for (long long j = (long long)i * i; j < MAXN; j += i) {
                is_prime[j] = false;
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    // Fix spf for numbers whose smallest prime factor is themselves
    for (int i = 2; i < MAXN; i++)
        if (spf[i] == 0) spf[i] = i; // i is prime

    // Collect primes and create index map
    vector<int> primes;
    unordered_map<int, int> pidx;
    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i]) {
            pidx[i] = primes.size();
            primes.push_back(i);
        }
    }
    int num_primes = primes.size();

    // For each prime, track current target and current n_p
    vector<i64> target_arr(num_primes, 0);
    vector<i64> np_arr(num_primes, 0);

    i64 current_max = 0;
    i64 S = 0;

    for (int i = 2; i <= 1000000; i++) {
        // Factorize i and update all prime factors
        int temp = i;
        while (temp > 1) {
            int p = spf[temp];
            int idx = pidx[p];
            int vp = 0;
            while (temp % p == 0) {
                temp /= p;
                vp++;
            }
            // v_p(i!) = v_p((i-1)!) + v_p(i), so target increases by E * v_p(i)
            target_arr[idx] += (i64)E * vp;
            np_arr[idx] = min_n_for_target(p, target_arr[idx]);
            if (np_arr[idx] > current_max) current_max = np_arr[idx];
        }

        if (i >= 10) {
            S = (S + current_max % MOD) % MOD;
        }
    }

    cout << S << endl;
    return 0;
}

Python project_euler/problem_320/solution.py

"""
Problem 320: Factorials Divisible by a Huge Integer

N(i) = smallest n such that (i!)^E | n!, where E = 1234567890.
S(u) = sum of N(i) for i = 10 to u.
Find S(1000000) mod 10^18.

Uses incremental tracking of prime targets with binary search,
exploiting the monotonicity of N(i).

Answer: 278157919195482643
"""

import sys

def solve():
    E = 1234567890
    MOD = 10**18
    MAXN = 1000001

    # Smallest prime factor sieve
    spf = list(range(MAXN))
    for i in range(2, int(MAXN**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i

    # Collect primes
    primes = [i for i in range(2, MAXN) if spf[i] == i]
    prime_idx = {p: idx for idx, p in enumerate(primes)}

    def legendre(n, p):
        """v_p(n!) = sum floor(n/p^k)"""
        s = 0
        pk = p
        while pk <= n:
            s += n // pk
            if pk > n // p:
                break
            pk *= p
        return s

    def min_n_for_target(p, target):
        """Smallest n with v_p(n!) >= target."""
        if target <= 0:
            return 0
        lo, hi = 0, target * p
        while lo < hi:
            mid = (lo + hi) // 2
            if legendre(mid, p) >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo

    num_primes = len(primes)
    target_arr = [0] * num_primes
    np_arr = [0] * num_primes
    current_max = 0
    S = 0

    for i in range(2, MAXN):
        # Factorize i and update prime factor targets
        temp = i
        while temp > 1:
            p = spf[temp]
            idx = prime_idx[p]
            vp = 0
            while temp % p == 0:
                temp //= p
                vp += 1
            target_arr[idx] += E * vp
            np_arr[idx] = min_n_for_target(p, target_arr[idx])
            if np_arr[idx] > current_max:
                current_max = np_arr[idx]

        if i >= 10:
            S = (S + current_max) % MOD

    print(S)

if __name__ == "__main__":
    solve()