Problem 231: The Prime Factorisation of Binomial Coefficients

Mathematical Foundation

Theorem (Legendre’s Formula). For any prime $p$ and positive integer $n$, the $p$-adic valuation of $n!$ is

where $s_p(n)$ denotes the sum of the digits of $n$ in base $p$.

Proof. Among $1, 2, \ldots, n$, exactly $\lfloor n/p \rfloor$ are divisible by $p$, exactly $\lfloor n/p^2 \rfloor$ are divisible by $p^2$, and so on. Each multiple of $p^i$ contributes at least $i$ factors of $p$ to $n!$. Counting each factor of $p$ once yields $v_p(n!) = \sum_{i \geq 1} \lfloor n/p^i \rfloor$. Writing $n$ in base $p$ as $n = \sum_{j} d_j p^j$, a telescoping computation gives $\sum_{i \geq 1} \lfloor n/p^i \rfloor = (n - s_p(n))/(p-1)$. $\square$

Lemma (Kummer’s Theorem). For primes $p$ and integers $0 \leq k \leq n$, the $p$-adic valuation of $\binom{n}{k}$ equals the number of carries when adding $k$ and $n - k$ in base $p$.

Proof. We have $v_p\!\left(\binom{n}{k}\right) = v_p(n!) - v_p(k!) - v_p((n-k)!)$. Applying Legendre’s formula:

The quantity $s_p(k) + s_p(n-k) - s_p(n)$ equals $(p-1)$ times the number of carries in the base-$p$ addition $k + (n-k) = n$, since each carry reduces the digit sum by exactly $p - 1$. $\square$

Corollary. The exponent of prime $p$ in $\binom{n}{k}$ is

The desired answer is $S = \sum_{p \leq n,\, p\text{ prime}} e_p \cdot p$.

Editorial

We iterate over p in primes. We first generate the primes required by the search, then enumerate the admissible combinations and retain only the values that satisfy the final test.

Pseudocode

    primes = sieve_of_eratosthenes(n)
    S = 0
    for p in primes:
        e = 0
        power = p
        While power <= n:
            e += floor(n / power) - floor(k / power) - floor((n - k) / power)
            power *= p
        S += e * p
    Return S

Complexity Analysis

• Time: $O(n \log \log n)$ for the Sieve of Eratosthenes, plus $O(\pi(n) \cdot \log_2 n)$ for computing exponents across all primes. Total: $O(n \log \log n)$.
• Space: $O(n)$ for the sieve array.

Answer

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

int main() {
    const int N = 20000000;
    const int K = 15000000;
    const int M = N - K; // 5000000

    // Sieve of Eratosthenes
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= N; j += i)
                is_prime[j] = false;
        }
    }

    // For each prime, compute exponent in C(N, K) using Legendre's formula
    long long answer = 0;
    for (int p = 2; p <= N; p++) {
        if (!is_prime[p]) continue;
        long long exp_val = 0;
        long long pk = p;
        while (pk <= N) {
            exp_val += N / pk - K / pk - M / pk;
            if (pk > N / p) break; // prevent overflow
            pk *= p;
        }
        answer += exp_val * p;
    }

    cout << answer << endl;
    return 0;
}

"""
Problem 231: The Prime Factorisation of Binomial Coefficients
Find the sum of terms in the prime factorisation of C(20000000, 15000000).
"""

def sieve(n):
    """Sieve of Eratosthenes returning list of primes up to n."""
    is_prime = bytearray(b'\x01') * (n + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return [i for i in range(2, n + 1) if is_prime[i]]

def exponent_in_factorial(n, p):
    """Compute the exponent of prime p in n! using Legendre's formula."""
    exp = 0
    pk = p
    while pk <= n:
        exp += n // pk
        pk *= p
    return exp

def solve():
    N = 20000000
    K = 15000000
    M = N - K  # 5000000

    primes = sieve(N)

    answer = 0
    for p in primes:
        e = exponent_in_factorial(N, p) - exponent_in_factorial(K, p) - exponent_in_factorial(M, p)
        if e > 0:
            answer += e * p

    print(answer)

if __name__ == "__main__":
    solve()