题目148：考察帕斯卡三角形

欧拉计划

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:

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⁹) rows of Pascal's triangle.

题目：

可以轻易验证，在帕斯卡三角形的前七行中没有任何数可以被 7 整除：

但是如果我们查看前 100 行，在 5050 个数中，一共有 2361 个不能被 7 整除。

求在帕斯卡三角形的前 10⁹ 行中共有多少个数不能被 7 整除。

永恒的蓝色梦想

3000多行的数据，加了格式

1 2 3 4 5 6 7 
2 4 6 8 10 12 14 
3 6 9 12 15 18 21 
4 8 12 16 20 24 28 
5 10 15 20 25 30 35 
6 12 18 24 30 36 42 
7 14 21 28 35 42 49 

2 4 6 8 10 12 14 
4 8 12 16 20 24 28 
6 12 18 24 30 36 42 
8 16 24 32 40 48 56 
10 20 30 40 50 60 70 
12 24 36 48 60 72 84 
14 28 42 56 70 84 98 

3 6 9 12 15 18 21 
6 12 18 24 30 36 42 
9 18 27 36 45 54 63 
12 24 36 48 60 72 84 
15 30 45 60 75 90 105 
18 36 54 72 90 108 126 
21 42 63 84 105 126 147 

4 8 12 16 20 24 28 
8 16 24 32 40 48 56 
12 24 36 48 60 72 84 
16 32 48 64 80 96 112 
20 40 60 80 100 120 140 
24 48 72 96 120 144 168 
28 56 84 112 140 168 196 

5 10 15 20 25 30 35 
10 20 30 40 50 60 70 
15 30 45 60 75 90 105 
20 40 60 80 100 120 140 
25 50 75 100 125 150 175 
30 60 90 120 150 180 210 
35 70 105 140 175 210 245 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

7 14 21 28 35 42 49 
14 28 42 56 70 84 98 
21 42 63 84 105 126 147 
28 56 84 112 140 168 196 
35 70 105 140 175 210 245 
42 84 126 168 210 252 294 
49 98 147 196 245 294 343 

2 4 6 8 10 12 14 
4 8 12 16 20 24 28 
6 12 18 24 30 36 42 
8 16 24 32 40 48 56 
10 20 30 40 50 60 70 
12 24 36 48 60 72 84 
14 28 42 56 70 84 98 

4 8 12 16 20 24 28 
8 16 24 32 40 48 56 
12 24 36 48 60 72 84 
16 32 48 64 80 96 112 
20 40 60 80 100 120 140 
24 48 72 96 120 144 168 
28 56 84 112 140 168 196 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

8 16 24 32 40 48 56 
16 32 48 64 80 96 112 
24 48 72 96 120 144 168 
32 64 96 128 160 192 224 
40 80 120 160 200 240 280 
48 96 144 192 240 288 336 
56 112 168 224 280 336 392 

10 20 30 40 50 60 70 
20 40 60 80 100 120 140 
30 60 90 120 150 180 210 
40 80 120 160 200 240 280 
50 100 150 200 250 300 350 
60 120 180 240 300 360 420 
70 140 210 280 350 420 490 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

14 28 42 56 70 84 98 
28 56 84 112 140 168 196 
42 84 126 168 210 252 294 
56 112 168 224 280 336 392 
70 140 210 280 350 420 490 
84 168 252 336 420 504 588 
98 196 294 392 490 588 686 

3 6 9 12 15 18 21 
6 12 18 24 30 36 42 
9 18 27 36 45 54 63 
12 24 36 48 60 72 84 
15 30 45 60 75 90 105 
18 36 54 72 90 108 126 
21 42 63 84 105 126 147 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

9 18 27 36 45 54 63 
18 36 54 72 90 108 126 
27 54 81 108 135 162 189 
36 72 108 144 180 216 252 
45 90 135 180 225 270 315 
54 108 162 216 270 324 378 
63 126 189 252 315 378 441 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

15 30 45 60 75 90 105 
30 60 90 120 150 180 210 
45 90 135 180 225 270 315 
60 120 180 240 300 360 420 
75 150 225 300 375 450 525 
90 180 270 360 450 540 630 
105 210 315 420 525 630 735 

18 36 54 72 90 108 126 
36 72 108 144 180 216 252 
54 108 162 216 270 324 378 
72 144 216 288 360 432 504 
90 180 270 360 450 540 630 
108 216 324 432 540 648 756 
126 252 378 504 630 756 882 

21 42 63 84 105 126 147 
42 84 126 168 210 252 294 
63 126 189 252 315 378 441 
84 168 252 336 420 504 588 
105 210 315 420 525 630 735 
126 252 378 504 630 756 882 
147 294 441 588 735 882 1029 

4 8 12 16 20 24 28 
8 16 24 32 40 48 56 
12 24 36 48 60 72 84 
16 32 48 64 80 96 112 
20 40 60 80 100 120 140 
24 48 72 96 120 144 168 
28 56 84 112 140 168 196 

8 16 24 32 40 48 56 
16 32 48 64 80 96 112 
24 48 72 96 120 144 168 
32 64 96 128 160 192 224 
40 80 120 160 200 240 280 
48 96 144 192 240 288 336 
56 112 168 224 280 336 392 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

16 32 48 64 80 96 112 
32 64 96 128 160 192 224 
48 96 144 192 240 288 336 
64 128 192 256 320 384 448 
80 160 240 320 400 480 560 
96 192 288 384 480 576 672 
112 224 336 448 560 672 784 

20 40 60 80 100 120 140 
40 80 120 160 200 240 280 
60 120 180 240 300 360 420 
80 160 240 320 400 480 560 
100 200 300 400 500 600 700 
120 240 360 480 600 720 840 
140 280 420 560 700 840 980 

24 48 72 96 120 144 168 
48 96 144 192 240 288 336 
72 144 216 288 360 432 504 
96 192 288 384 480 576 672 
120 240 360 480 600 720 840 
144 288 432 576 720 864 1008 
168 336 504 672 840 1008 1176 

28 56 84 112 140 168 196 
56 112 168 224 280 336 392 
84 168 252 336 420 504 588 
112 224 336 448 560 672 784 
140 280 420 560 700 840 980 
168 336 504 672 840 1008 1176 
196 392 588 784 980 1176 1372 

5 10 15 20 25 30 35 
10 20 30 40 50 60 70 
15 30 45 60 75 90 105 
20 40 60 80 100 120 140 
25 50 75 100 125 150 175 
30 60 90 120 150 180 210 
35 70 105 140 175 210 245 

10 20 30 40 50 60 70 
20 40 60 80 100 120 140 
30 60 90 120 150 180 210 
40 80 120 160 200 240 280 
50 100 150 200 250 300 350 
60 120 180 240 300 360 420 
70 140 210 280 350 420 490 

15 30 45 60 75 90 105 
30 60 90 120 150 180 210 
45 90 135 180 225 270 315 
60 120 180 240 300 360 420 
75 150 225 300 375 450 525 
90 180 270 360 450 540 630 
105 210 315 420 525 630 735 

20 40 60 80 100 120 140 
40 80 120 160 200 240 280 
60 120 180 240 300 360 420 
80 160 240 320 400 480 560 
100 200 300 400 500 600 700 
120 240 360 480 600 720 840 
140 280 420 560 700 840 980 

25 50 75 100 125 150 175 
50 100 150 200 250 300 350 
75 150 225 300 375 450 525 
100 200 300 400 500 600 700 
125 250 375 500 625 750 875 
150 300 450 600 750 900 1050 
175 350 525 700 875 1050 1225 

30 60 90 120 150 180 210 
60 120 180 240 300 360 420 
90 180 270 360 450 540 630 
120 240 360 480 600 720 840 
150 300 450 600 750 900 1050 
180 360 540 720 900 1080 1260 
210 420 630 840 1050 1260 1470 

35 70 105 140 175 210 245 
70 140 210 280 350 420 490 
105 210 315 420 525 630 735 
140 280 420 560 700 840 980 
175 350 525 700 875 1050 1225 
210 420 630 840 1050 1260 1470 
245 490 735 980 1225 1470 1715 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

18 36 54 72 90 108 126 
36 72 108 144 180 216 252 
54 108 162 216 270 324 378 
72 144 216 288 360 432 504 
90 180 270 360 450 540 630 
108 216 324 432 540 648 756 
126 252 378 504 630 756 882 

24 48 72 96 120 144 168 
48 96 144 192 240 288 336 
72 144 216 288 360 432 504 
96 192 288 384 480 576 672 
120 240 360 480 600 720 840 
144 288 432 576 720 864 1008 
168 336 504 672 840 1008 1176 

30 60 90 120 150 180 210 
60 120 180 240 300 360 420 
90 180 270 360 450 540 630 
120 240 360 480 600 720 840 
150 300 450 600 750 900 1050 
180 360 540 720 900 1080 1260 
210 420 630 840 1050 1260 1470 

36 72 108 144 180 216 252 
72 144 216 288 360 432 504 
108 216 324 432 540 648 756 
144 288 432 576 720 864 1008 
180 360 540 720 900 1080 1260 
216 432 648 864 1080 1296 1512 
252 504 756 1008 1260 1512 1764 

42 84 126 168 210 252 294 
84 168 252 336 420 504 588 
126 252 378 504 630 756 882 
168 336 504 672 840 1008 1176 
210 420 630 840 1050 1260 1470 
252 504 756 1008 1260 1512 1764 
294 588 882 1176 1470 1764 2058 

7 14 21 28 35 42 49 
14 28 42 56 70 84 98 
21 42 63 84 105 126 147 
28 56 84 112 140 168 196 
35 70 105 140 175 210 245 
42 84 126 168 210 252 294 
49 98 147 196 245 294 343 

14 28 42 56 70 84 98 
28 56 84 112 140 168 196 
42 84 126 168 210 252 294 
56 112 168 224 280 336 392 
70 140 210 280 350 420 490 
84 168 252 336 420 504 588 
98 196 294 392 490 588 686 

21 42 63 84 105 126 147 
42 84 126 168 210 252 294 
63 126 189 252 315 378 441 
84 168 252 336 420 504 588 
105 210 315 420 525 630 735 
126 252 378 504 630 756 882 
147 294 441 588 735 882 1029 

28 56 84 112 140 168 196 
56 112 168 224 280 336 392 
84 168 252 336 420 504 588 
112 224 336 448 560 672 784 
140 280 420 560 700 840 980 
168 336 504 672 840 1008 1176 
196 392 588 784 980 1176 1372 

35 70 105 140 175 210 245 
70 140 210 280 350 420 490 
105 210 315 420 525 630 735 
140 280 420 560 700 840 980 
175 350 525 700 875 1050 1225 
210 420 630 840 1050 1260 1470 
245 490 735 980 1225 1470 1715 

42 84 126 168 210 252 294 
84 168 252 336 420 504 588 
126 252 378 504 630 756 882 
168 336 504 672 840 1008 1176 
210 420 630 840 1050 1260 1470 
252 504 756 1008 1260 1512 1764 
294 588 882 1176 1470 1764 2058 

49 98 147 196 245 294 343 
98 196 294 392 490 588 686 
147 294 441 588 735 882 1029 
196 392 588 784 980 1176 1372 
245 490 735 980 1225 1470 1715 
294 588 882 1176 1470 1764 2058 
343 686 1029 1372 1715 2058 2401 

2 4 6 8 10 12 14 
4 8 12 16 20 24 28 
6 12 18 24 30 36 42 
8 16 24 32 40 48 56 
10 20 30 40 50 60 70 
12 24 36 48 60 72 84 
14 28 42 56 70 84 98 

4 8 12 16 20 24 28 
8 16 24 32 40 48 56 
12 24 36 48 60 72 84 
16 32 48 64 80 96 112 
20 40 60 80 100 120 140 
24 48 72 96 120 144 168 
28 56 84 112 140 168 196 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

8 16 24 32 40 48 56 
16 32 48 64 80 96 112 
24 48 72 96 120 144 168 
32 64 96 128 160 192 224 
40 80 120 160 200 240 280 
48 96 144 192 240 288 336 
56 112 168 224 280 336 392 

10 20 30 40 50 60 70 
20 40 60 80 100 120 140 
30 60 90 120 150 180 210 
40 80 120 160 200 240 280 
50 100 150 200 250 300 350 
60 120 180 240 300 360 420 
70 140 210 280 350 420 490 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

14 28 42 56 70 84 98 
28 56 84 112 140 168 196 
42 84 126 168 210 252 294 
56 112 168 224 280 336 392 
70 140 210 280 350 420 490 
84 168 252 336 420 504 588 
98 196 294 392 490 588 686 

4 8 12 16 20 24 28 
8 16 24 32 40 48 56 
12 24 36 48 60 72 84 
16 32 48 64 80 96 112 
20 40 60 80 100 120 140 
24 48 72 96 120 144 168 
28 56 84 112 140 168 196 

8 16 24 32 40 48 56 
16 32 48 64 80 96 112 
24 48 72 96 120 144 168 
32 64 96 128 160 192 224 
40 80 120 160 200 240 280 
48 96 144 192 240 288 336 
56 112 168 224 280 336 392 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

16 32 48 64 80 96 112 
32 64 96 128 160 192 224 
48 96 144 192 240 288 336 
64 128 192 256 320 384 448 
80 160 240 320 400 480 560 
96 192 288 384 480 576 672 
112 224 336 448 560 672 784 

20 40 60 80 100 120 140 
40 80 120 160 200 240 280 
60 120 180 240 300 360 420 
80 160 240 320 400 480 560 
100 200 300 400 500 600 700 
120 240 360 480 600 720 840 
140 280 420 560 700 840 980 

24 48 72 96 120 144 168 
48 96 144 192 240 288 336 
72 144 216 288 360 432 504 
96 192 288 384 480 576 672 
120 240 360 480 600 720 840 
144 288 432 576 720 864 1008 
168 336 504 672 840 1008 1176 

28 56 84 112 140 168 196 
56 112 168 224 280 336 392 
84 168 252 336 420 504 588 
112 224 336 448 560 672 784 
140 280 420 560 700 840 980 
168 336 504 672 840 1008 1176 
196 392 588 784 980 1176 1372 

6 12 18 24 30 36 42 
12 24 36 48 60 72 84 
18 36 54 72 90 108 126 
24 48 72 96 120 144 168 
30 60 90 120 150 180 210 
36 72 108 144 180 216 252 
42 84 126 168 210 252 294 

12 24 36 48 60 72 84 
24 48 72 96 120 144 168 
36 72 108 144 180 216 252 
48 96 144 192 240 288 336 
60 120 180 240 300 360 420 
72 144 216 288 360 432 504 
84 168 252 336 420 504 588 

18 36 54 72 90 108 126 
36 72 108 144 180 216 252 
54 108 162 216 270 324 378 
72 144 216 288 360 432 504 
90 180 270 360 450 540 630 
108 216 324 432 540 648 756 
126 252 378 504 630 756 882 

24 48 72 96 120 144 168 
48 96 144 192 240 288 336 
72 144 216 288 360 432 504 
96 192 288 384 480 576 672 
120 240 360 480 600 720 840 
144 288 432 576 720 864 1008 
168 336 504 672 840 1008 1176 

30 60 90 120 150 180 210 
60 120 180 240 300 360 420 
90 180 270 360 450 540 630 
120 240 360 480 600 720 840 
150 300 450 600 750 900 1050 
180 360 540 720 900 1080 1260 
210 420 630 840 1050 1260 1470 

36 72 108 144 180 216 252 
72 144 216 288 360 432 504 
108 216 324 432 540 648 756 
144 288 432 576 720 864 1008 
180 360 540 720 900 1080 1260 
216 432 648 864 1080 1296 1512 
252 504 756 1008 1260 1512 1764 

42 84 126 168 210 252 294 
84 168 252 336 420 504 588 
126 252 378 504 630 756 882 
168 336 504 672 840 1008 1176 
210 420 630 840 1050 1260 1470 
252 504 756 1008 1260 1512 1764 
294 588 882 1176 1470 1764 2058 

8 16 24 32 40 48 56 
16 32 48 64 80 96 112 
24 48 72 96 120 144 168 
32 64 96 128 160 192 224 
40 80 120 160 200 240 280 
48 96 144 192 240 288 336 
56 112 168 224 280 336 392 

16 32 48 64 80 96 112 
32 64 96 128 160 192 224 
48 96 144 192 240 288 336 
64 128 192 256 320 384 448 
80 160 240 320 400 480 560 
96 192 288 384 480 576 672 
112 224 336 448 560 672 784 

24 48 72 96 120 144 168 
48 96 144 192 240 288 336 
72 144 216 288 360 432 504 
96 192 288 384 480 576 672 
120 240 360 480 600 720 840 
144 288 432 576 720 864 1008 
168 336 504 672 840 1008 1176 

32 64 96 128 160 192 224 
64 128 192 256 320 384 448 
96 192 288 384 480 576 672 
128 256 384 512 640 768 896 
160 320 480 640 800 960 1120 
192 384 576 768 960 1152 1344 
224 448 672 896 1120 1344 1568 

40 80 120 160 200 240 280 
80 160 240 320 400 480 560 
120 240 360 480 600 720 840 
160 320 480 640 800 960 1120 
200 400 600 800 1000 1200 1400 
240 480 720 960 1200 1440 1680 
280 560 840 1120 1400 1680 1960 

48 96 144 192 240 288 336 
96 192 288 384 480 576 672 
144 288 432 576 720 864 1008 
192 384 576 768 960 1152 1344 
240 480 720 960 1200 1440 1680 
288 576 864 1152 1440 1728 2016 
336 672 1008 1344 1680 2016 2352 

56 112 168 224 280 336 392 
112 224 336 448 560 672 784 
168 336 504 672 840 1008 1176 
224 448 672 896 1120 1344 1568 
280 560 840 1120 1400 1680 1960 
336 672 1008 1344 1680 2016 2352 
392 784 1176 1568 1960 2352 2744 

10 20 30 40 50 60 70 
20 40 60 80 100 120 140 
30 60 90 120 150 180 210 
40 80 120 160 200 240 280 
50 100 150 200 250 300 350 
60 120 180 240 300 360 420 
70 140 210 280 350 420 490 

20 40 60 80 100 120 140 
40 80 120 160 200 240 280 
60 120 180 240 300 360 420 
80 160 240 320 400 480 560 
100 200 300 400 500 600 700 
120 240 360 480 600 720 840 
140 280 420 560 700 840 980 

30 60 90 120 150 180 210 
60 120 180 240 300 360 420 
90 180 270 360 450 540 630 
120 240 360 480 600 720 840 
150 300 450 600 750 900 1050 
180 360 540 720 900 1080 1260 
210 420 630 840 1050 1260 1470 

40 80 120 160 200 240 280 
80 160 240 320 400 480 560 
120 240 360 480 600 720 840 
160 320 480 640 800 960 1120 
200 400 600 800 1000 1200 1400 
240 480 720 960 1200 1440 1680 
280 560 840 1120 1400 1680 1960 

50 100 150 200 250 300 350 
100 200 300 400 500 600 700 
150 300 450 600 750 900 1050 
200 400