Project Euler Problem 148

Solution

Answer: 2129970655314432

Let row $n$ of Pascal’s triangle be

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

We want the number of entries not divisible by $7$ among the first $10^9$ rows (rows $0$ through $10^9-1$).

The key tool is Lucas’ Theorem.

---

1. Mathematical Analysis

Step 1 — Lucas’ Theorem

For a prime $p$,

$$\binom{n}{k} \not\equiv 0 \pmod p$$

iff every base-$p$ digit of $k$ is at most the corresponding digit of $n$.

Write

$$n = n_r n_{r-1}\dots n_0 \quad \text{(base }7\text{)}.$$

Then the number of coefficients in row $n$ not divisible by $7$ is

$$\prod_{i=0}^{r}(n_i+1).$$

Why?

For each digit position $i$, the digit $k_i$ may be any integer

$$0 \le k_i \le n_i,$$

giving exactly $n_i+1$ choices independently.

Therefore:

$$f(n)=#{\text{entries in row }n\text{ not divisible by }7} =\prod (n_i+1).$$

---

Step 2 — Small Example

Take $n=6$.

In base $7$,

$$6 = (6)_7.$$

So

$$f(6)=6+1=7.$$

Indeed row 6 is:

$$1,\ 6,\ 15,\ 20,\ 15,\ 6,\ 1$$

and none are divisible by 7.

---

Take $n=8$.

$$8=(11)_7.$$

Thus

$$f(8)=(1+1)(1+1)=4.$$

Indeed row 8 has only 4 entries not divisible by 7.

---

2. Summing Efficiently

We need

$$S(N)=\sum_{n=0}^{N-1} f(n),$$

with $N=10^9$.

---

Step 3 — Full blocks

Consider all numbers with at most $m$ base-7 digits:

$$0 \le n < 7^m.$$

Then

$$S(7^m) = \sum_{n_0=0}^{6}\cdots\sum_{n_{m-1}=0}^{6} \prod (n_i+1).$$

Because the product separates:

$$S(7^m) = \left(\sum_{d=0}^{6}(d+1)\right)^m.$$

But

$$1+2+3+4+5+6+7 = 28.$$

Hence

$$S(7^m)=28^m.$$

This is the crucial simplification.

---

3. Recursive Digit DP

Now write $N$ in base 7.

We process digits from most significant to least significant.

Suppose the current digit is $d$, and we already accumulated a multiplicative prefix $P$.

For smaller leading digits $x<d$:

• remaining positions count:

$$28^{\text{remaining digits}}$$

• contribution from current digit:

$$(x+1)$$

• contribution from previous digits:

$$P$$

So we add

$$P \cdot (1+2+\cdots+d)\cdot 28^r.$$

Then continue with:

$$P \leftarrow P(d+1).$$

---

4. Base-7 Representation of $10^9$

Compute powers:

$$7^{10}=282475249,$$

$$7^{11}=1977326743.$$

Thus $10^9$ has 11 base-7 digits.

Converting:

$$10^9=(3353160061)_7.$$

Digits:

$$3,3,5,3,1,6,0,0,6,1.$$

(leading zero omitted).

---

5. Python Implementation

def count_not_divisible(N, p=7):
    """
    Returns the number of entries not divisible by p
    in the first N rows of Pascal's triangle.
    """

    # Convert N to base p digits
    digits = []
    x = N
    while x > 0:
        digits.append(x % p)
        x //= p

    digits.reverse()

    # Precompute powers of 28
    # because sum_{d=0}^{6} (d+1) = 28
    powers = [1]
    for _ in range(len(digits)):
        powers.append(powers[-1] * 28)

    ans = 0
    prefix_product = 1
    m = len(digits)

    for i, d in enumerate(digits):
        remaining = m - i - 1

        # Sum of (x+1) for x = 0..d-1
        # = d(d+1)/2
        smaller_sum = d * (d + 1) // 2

        ans += (
            prefix_product
            * smaller_sum
            * powers[remaining]
        )

        # Extend prefix with actual digit
        prefix_product *= (d + 1)

    return ans

print(count_not_divisible(10**9))

---

6. Code Walkthrough

Base conversion

while x > 0:
    digits.append(x % p)
    x //= p

Converts $N$ into base 7.

---

Precomputing powers

powers.append(powers[-1] * 28)

Uses:

$$S(7^m)=28^m.$$

---

Main loop

At each digit:

smaller_sum = d * (d + 1) // 2

because

$$1+2+\cdots+d=\frac{d(d+1)}{2}.$$

Then:

ans += prefix_product * smaller_sum * powers[remaining]

counts all numbers with a smaller digit at this position.

Finally:

prefix_product *= (d + 1)

extends the valid prefix.

---

7. Verify on Small Example

For the first 7 rows:

$$S(7)=28.$$

Indeed total entries are:

$$1+2+3+4+5+6+7=28,$$

and none are divisible by 7.

---

For the first 100 rows:

Running the code gives:

$$2361,$$

matching the statement.

---

8. Final Computation

Evaluating for

$$N=10^9$$

gives

$$2129970655314432.$$

This is plausible:

• total entries are roughly

$$\frac{10^9(10^9+1)}{2}\approx 5\times10^{17},$$

• only a small fractal proportion survive divisibility by 7,
• result magnitude $\approx 2\times10^{15}$ is reasonable.

---

Answer: 2129970655314432