Solution

Answer: 7526965179680

We want the sum of the prime factors (with multiplicity) of

$$\binom{20,000,000}{15,000,000}.$$

Equivalently, if

$$\binom{n}{k}=\prod_p p^{e_p},$$

we seek

$$\sum_p p,e_p.$$

For the small example,

$$\binom{10}{3}=120=2^3\cdot3\cdot5,$$

so the required sum is

$$2\cdot3+3\cdot1+5\cdot1=14.$$

1. Mathematical analysis

The key idea is to compute the exponent of each prime in a factorial using Legendre’s formula.

For a prime $p$,

$$v_p(n!)=\sum_{i\ge1}\left\lfloor \frac{n}{p^i}\right\rfloor.$$

Therefore,

$$v_p!\left(\binom{n}{k}\right) = v_p(n!) - v_p(k!) - v_p((n-k)!).$$

For this problem:

$$n=20,000,000,\qquad k=15,000,000,\qquad n-k=5,000,000.$$

Hence

$$e_p = \sum_{i\ge1} \left( \left\lfloor \frac{20,000,000}{p^i}\right\rfloor - \left\lfloor \frac{15,000,000}{p^i}\right\rfloor - \left\lfloor \frac{5,000,000}{p^i}\right\rfloor \right).$$

The desired answer is

$$\sum_{p\le 20,000,000} p,e_p.$$

So the algorithm is:

Generate all primes up to $20,000,000$ using a sieve.
For each prime $p$:

Compute $e_p$ with Legendre’s formula.
Add $p\cdot e_p$ to the total.

This is efficient because:

there are only about $1.27$ million primes up to $20$ million,
and each prime contributes only $O(\log_p n)$ terms.

2. Python implementation

from math import isqrt

N = 20_000_000
K = 15_000_000

# ---------------------------------------------------------
# Sieve of Eratosthenes
# ---------------------------------------------------------
# Generate all primes <= N
sieve = bytearray(b"\x01") * (N + 1)
sieve[0:2] = b"\x00\x00"

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

primes = [i for i in range(2, N + 1) if sieve[i]]

# ---------------------------------------------------------
# Legendre exponent for p in n!
# ---------------------------------------------------------
def vp_factorial(n, p):
    total = 0
    while n:
        n //= p
        total += n
    return total

# ---------------------------------------------------------
# Compute the required sum
# ---------------------------------------------------------
answer = 0

for p in primes:
    exponent = (
        vp_factorial(N, p)
        - vp_factorial(K, p)
        - vp_factorial(N - K, p)
    )

    answer += p * exponent

print(answer)

3. Code walkthrough

Sieve section

sieve = bytearray(b"\x01") * (N + 1)

Creates a boolean array marking all numbers as potentially prime.

sieve[0:2] = b"\x00\x00"

Marks 0 and 1 as non-prime.

for i in range(2, isqrt(N) + 1):

Standard sieve loop up to $\sqrt N$.

sieve[start:N + 1:step] = ...

Marks multiples of $i$ as composite.

Finally:

primes = [i for i in range(2, N + 1) if sieve[i]]

collects all primes.

Legendre exponent

def vp_factorial(n, p):

Computes $v_p(n!)$.

The loop:

n //= p
total += n

implements

$$\left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor + \left\lfloor \frac{n}{p^3}\right\rfloor+\cdots$$

until the quotient becomes zero.

Binomial exponent

exponent = (
    vp_factorial(N, p)
    - vp_factorial(K, p)
    - vp_factorial(N - K, p)
)

uses

$$v_p!\left(\binom{N}{K}\right) = v_p(N!) -v_p(K!) -v_p((N-K)!).$$

Then:

answer += p * exponent

adds the sum of prime factors with multiplicity.

4. Small-example verification

Take

$$\binom{10}{3}=120.$$

Prime exponents:

$v_2(10!)=5+2+1=8$
$v_2(3!)=1$
$v_2(7!)=3+1=4$

So exponent of 2 is

$$8-1-4=3.$$

Similarly:

exponent of 3 is $1$,
exponent of 5 is $1$.

Thus

$$2\cdot3 + 3\cdot1 + 5\cdot1 = 6+3+5 = 14,$$

matching the statement.

5. Final verification

The answer must be large and positive because:

many primes divide the binomial coefficient,
exponents are nonnegative integers,
and the scale should be on the order of $10^{13}$–$10^{14}$.

Running the computation yields:

$$7526965179680.$$

Answer: 7526965179680

Project Euler Problem 231