For project Euler 148 problem, I want to get the amount of numbers in Pascals Triangle that are not divisible by 7 in row 0 to n where n is $10^9$.
Find the number of entries which are not divisible by 7 in the first one billion (109) rows of Pascal's triangle.
I did that by iterating all numbers from 0 to n. For each iteration, convert n to base 7, add 1 to each digit and multiply them after that. This gives me all the numbers that are not divisible by 7 in that row. I add the result then to the total sum.
The question I have, is there another method that doesn't require the iteration of all the numbers from 0 to n? I found an article that does it somehow by making use of triangular numbers:
Take a look at $10^9$ in base 7: $10_{10}^9=33531600616_7$
If our base 7 number was actually 30000000000, then all would need to do is calculate $T3$, then multiply by $28^n$, where n is the number of digits after the digit in question (in this case, there are 10 following digits). The 28 comes from $T7$, which arises from each digit effectively contributing the sum of 1 to 7. Thus, if 148 posed the problem for $30000000000_7$ rows, the answer would be $T3×28^{10}=1777180600172544$.
However, our problem is slightly more complicated, as there are other digits. Move onto the next one: $33000000000_7$ We add our previous result to this one ($T3×28^9$), but we need to incorporate the fact that we’ve “added onto” the most significant digit. This is done by simply multiplying this digit’s contribution by all previous digits plus 1, like so: […]
But I don't really understand how it was done. How can you make use of the triangular numbers to find the sum of numbers not divisible by 7 in all rows of Pascals Triangle up to row $10^9$.
EDIT
I created a program that outputs the first 35 rows of the triangle and highlights numbers that are divisible by 7.
0 [0]
1 [0,0]
2 [0,0,0]
3 [0,0,0,0]
4 [0,0,0,0,0]
5 [0,0,0,0,0,0]
6 [0,0,0,0,0,0,0]
7 [0,1,1,1,1,1,1,0]
8 [0,0,1,1,1,1,1,0,0]
9 [0,0,0,1,1,1,1,0,0,0]
10 [0,0,0,0,1,1,1,0,0,0,0]
11 [0,0,0,0,0,1,1,0,0,0,0,0]
12 [0,0,0,0,0,0,1,0,0,0,0,0,0]
13 [0,0,0,0,0,0,0,0,0,0,0,0,0,0]
14 [0,1,1,1,1,1,1,0,1,1,1,1,1,1,0]
15 [0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0]
16 [0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0]
17 [0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0]
18 [0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0]
19 [0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0]
20 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
21 [0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0]
22 [0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0]
23 [0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0]
24 [0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0]
25 [0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0]
26 [0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0]
27 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
28 [0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0]
29 [0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0]
30 [0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0]
31 [0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0]
32 [0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0]
33 [0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0]
34 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Including the row number 33 in that diagram, I can see that there are 10 triangles there, which have $21 = T6$ ones. What I don't understand is how this helps getting the sum of all the numbers divisible by 7, because each triangle contains different numbers.
Best Answer
Assuming you do not need rigorous, mathematical justification, you can simply do it in the following way:
First, find $n = \dfrac{10^9}{7}=142857142$. Then there will be in total of $ T_n = \dfrac{n(n+1)}{2}$ triangular block of consisting of $1's$. As you demonstrated in your code, each of those block has exactly $T_6 = 21$ $1's$, so there are $N = 21T_n$ numbers that are divisible by $7$ in the first $10^9$ rows of the Pascal triangle. Once you have found this, the answer to actual problem will simply be $1+2+...+10^9 - N$, obviously.
Last but not least, notice that how the only rows that has no $1's$ are the rows numbered $6, 13, 20,...$. In fact, this pattern continues and $10^9$ th row will precisely be another zero row because $10^9= -1\mod 7.$ Therefore, you do not need to worry about half triangle appearing at the very bottom. I am certain that the number $10^9$ was chosen for this particular purpose.
One can prove all these assertions mathematically, but you need at least Lucas's theorem, or some equivalent machinery which in general assumes a very decent knowledge of number theory. The author of that article you mentioned did a very poor job of attempting explain the reasoning.