Exploring Pascal’s Triangle

We can easily verify that none of the entries in the first seven rows of Pascal’s triangle are divisible by $7$:

$1$

$1$

$1$

$1$

$2$

$1$

$1$

$3$

$3$

$1$

$1$

$4$

$6$

$4$

$1$

$1$

$5$

$10$

$10$

$5$

$1$

$1$

$6$

$15$

$20$

$15$

$6$

$1$

However, if we check the first one hundred rows, we will find that only $2361$ of the $5050$ entries are not divisible by $7$.
Find the number of entries which are not divisible by $7$ in the first one billion ($10^9$) rows of Pascal’s triangle.

To solve this, we need to understand a concept called Mathematical Induction and a property of Pascal’s triangle. Here’s a generalized explanation:

We can write a natural number $n$ ($10^9$ in this case) in the format $n = a_0*7^0 + a_1*7^1 + a_2*7^2 + a_3*7^3 + … + a_k*7^k$, where each $a_n$ is an integer between 0 to 6 (inclusive). This is essentially the number representation in base 7. Now think about entries of row $n$ in Pascal’s triangle. By definition, we know it includes $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ where $0 \leq r \leq n$.

To find the number of non-divisible entries by 7 in the Pascal triangle, we can express the row and column in base 7. If for each digit, the value is less than or equal to the corresponding digit of the row number when both numbers are written in base 7, then this entry is non-divisible by 7.

So in each row, there are $1+(a_0 + 1)(a_1 + 1)(a_2 + 1)…(a_k + 1)$ non-divisible entries.

To find the total number of non-divisible entries by 7 in the first $10^9$ rows, you should calculate the sum of non-divisible numbers in each row from 0 to $10^9$. Because you have the expression of this sum for row $n$, you can just plug in the corresponding values and sum up every row.

However, you should be aware that directly computing this might not be feasible due to the enormous size (large computation). For that reason, you may need programming or software assisting in the calculation or finding a more concise mathematical way before calculation. Please remember that this problem requires deep mathematical understanding and computation skill.

More Answers: