Project Euler Problem 53

Solution

Answer: 4075

We must count how many binomial coefficients

$$\binom{n}{r}$$

with $1 \le n \le 100$ are greater than $1{,}000{,}000$.

---

Mathematical analysis

The binomial coefficient is

$$\binom{n}{r}=\frac{n!}{r!(n-r)!}.$$

A direct computation using factorials is possible, but there is a more important structural observation.

1. Symmetry of binomial coefficients

We have the identity

$$\binom{n}{r}=\binom{n}{n-r}.$$

So values are symmetric around $r=n/2$.

For example,

$$\binom{23}{10}=\binom{23}{13}.$$

This symmetry helps reduce work.

---

2. Growth behavior

For fixed $n$, the sequence

$$\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$$

increases up to the middle and then decreases symmetrically.

Therefore, once a coefficient exceeds one million, all coefficients closer to the middle will also exceed one million.

So for each $n$:

1. Find the first $r$ such that

$$\binom{n}{r} > 1{,}000{,}000.$$

1. Then all values from $r$ through $n-r$ exceed one million.

Hence the count contributed by that row is

$$(n-r) - r + 1 = n - 2r + 1.$$

---

3. Efficient recurrence

Instead of factorials, compute coefficients iteratively using

$$\binom{n}{r} = \binom{n}{r-1}\cdot\frac{n-r+1}{r}.$$

This avoids huge factorial computations.

Start with

$$\binom{n}{0}=1.$$

Then repeatedly generate the next coefficient.

---

Python implementation

# Count binomial coefficients greater than one million

LIMIT = 1_000_000
count = 0

# Loop through all n from 1 to 100
for n in range(1, 101):

    # Start with C(n,0) = 1
    c = 1

    # Compute coefficients iteratively
    for r in range(1, n + 1):

        # Recurrence relation:
        # C(n,r) = C(n,r-1) * (n-r+1) / r
        c = c * (n - r + 1) // r

        # Once we exceed the limit,
        # all coefficients up to C(n,n-r) also exceed it
        if c > LIMIT:
            count += (n - 2 * r + 1)
            break

print(count)

---

Code walkthrough

Initialization

LIMIT = 1_000_000
count = 0

We store the threshold and initialize the total count.

---

Loop over all rows

for n in range(1, 101):

We examine every row of Pascal’s triangle from $n=1$ to $100$.

---

Start with $\binom{n}{0}$

c = 1

Because

$$\binom{n}{0}=1.$$

---

Generate coefficients iteratively

c = c * (n - r + 1) // r

This computes

$$\binom{n}{r}$$

from the previous coefficient.

Example for $n=5$:

$$1,\ 5,\ 10,\ 10,\ 5,\ 1.$$

---

Detect first coefficient exceeding one million

if c > LIMIT:

Suppose this first occurs at position $r$.

By symmetry and monotonicity, every coefficient from $r$ to $n-r$ also exceeds the limit.

So we add

count += (n - 2 * r + 1)

which equals the number of terms in that interval.

Then:

break

because the rest of the row is already accounted for.

---

Small-example verification

The problem states:

$$\binom{23}{10} = 1144066 > 1{,}000{,}000.$$

Indeed, for $n=23$, the first exceeding coefficient occurs at $r=10$.

By symmetry:

$$\binom{23}{10}, \binom{23}{11}, \binom{23}{12}, \binom{23}{13}$$

all exceed one million.

Count:

$$23 - 2(10) + 1 = 4,$$

which matches.

---

Final verification

• We checked all $1 \le n \le 100$.
• Symmetry guarantees no overcounting or undercounting.
• The iterative recurrence avoids numerical instability.
• The known Project Euler result for this problem is consistent with the computation.

Answer: 4075