9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe it is simpler to sum the numbers that are divisible by $7$? $\endgroup$ – Hagen von Eitzen Apr 17 '17 at 9:23
  • $\begingroup$ @HagenvonEitzen can you explain a bit more? Like, I should try to find the amount of triangular numbers in $10^9$? $\endgroup$ – Max Apr 17 '17 at 9:47
  • $\begingroup$ I think he means, to find the sum of numbers not divisible by $7$, we only need to find the sum of all numbers (which is easy) minus the sum of the numbers divisible by $7$. This may be easier because there are "less" numbers divisible by $7$ than not $\endgroup$ – vrugtehagel Apr 17 '17 at 10:19
  • $\begingroup$ @vrugtehagel I see, I think I get the general idea. I can see how I can sum n rows of Pascals triangle by using powers of two, but can you give me a hint how to sum all the numbers divisible by 7? It doesn't seem straightforward as there are a different amount of powers of 7 per row (or none). $\endgroup$ – Max Apr 18 '17 at 1:00
  • 2
    $\begingroup$ Yeah I read that and I don't think it applies to me. $\endgroup$ – Max Apr 26 '17 at 2:11
0
$\begingroup$

This is only some simplified ideas.

  1. The sum of elements of $m$-th string is $2^m,$ so the total sum for the first $m$ strings is $2^{m+1} - 2.$
  2. When subtracting the "extra" elements of a triangle, the relations $$\genfrac{(}{)}{0}{}{m}{k} + \genfrac{(}{)}{0}{}{m}{k+1} = \genfrac{(}{)}{0}{}{m+1}{k+1}$$ can be used, which reduce the amount of operations by half.
  3. Recurrent calculations can be implemented due to formulas $$\genfrac{(}{)}{0}{}{m}{k+2} = \genfrac{(}{)}{0}{}{m}{k}\cdot\dfrac{(k+1)(k+2)}2,$$ $$\genfrac{(}{)}{0}{}{m+1}{k} = \genfrac{(}{)}{0}{}{m}{k} \cdot\dfrac{m+1}{m+1-k}.$$
  4. Also the mirror symmetry in rows can be used.

enter image description here

But I'm not sure that it can help in the general task.

$\endgroup$
  • $\begingroup$ Yuri, thanks for your input. My question title was ambigious, I was actually interested in the amout of numbers not divisible by 7, but without iteration. $\endgroup$ – Max May 2 '17 at 1:39
0
$\begingroup$

As vrugtehagel pointed out, the Pascal triangle $\mod p$ has a fractal structure. If you look at it long and strong enough, you can deduce the formula mentioned in Aryabhata's comment. (It can be extended to $\mod {p^n}$, and to $\mod n$ through the Chinese Reminder Theorem.)

Because it is a fractal you can deduce a formula for the number of non-zero-reminders at any "level" of the fractal...

$\endgroup$
0
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I give you the bounty because I found your explanation the most clear one, as compared to the one in the article. I would still be interested in the mathematical justification. :) $\endgroup$ – Max May 3 '17 at 1:15
  • $\begingroup$ This approach only works until row 48 (when counting the rows from 0). After that the pattern with the triangle repeats in itself. Looks pretty cool, but makes this idea not usable). $\endgroup$ – Max May 15 '17 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.