题目
We can easily verify that none of the entries in the first seven rows of Pascal’s triangle are divisible by:
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 (109) rows of Pascal’s triangle.
解答
这道题首先是帕斯卡三角，我们是叫杨辉三角。
杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年。— 百度百科
杨辉三角
我们首先定义一个函数来生成杨辉三角：
def triangles():
b = [1]
result = b.copy()
while True:
yield result
b.append(0)
result = [sum(x) for x in zip(*(b[1:],b[:-1]))]
result.insert(0,1)
b = result.copy()
- 我们不一次性生成整个三角型数据，浪费内存。我们只生成行，而只要有当下行，就能生成下一行。
- 写成一个生成器，这样可以写成个死循环，想生成多少行就生成多少行。
那么我们跑一下，生成前10行来看看：
>>> n = 0
>>> result = []
>>> for row in triangles():
... result.append(row)
... n = n + 1
... if n == 10:
... break
...
>>> for t in result:
... print(t)
...
[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]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
不能整除7的数目
这个难不倒我们，模7，余数>0便是不能整除，一行一行过，计个数嘛，这有何难。正好题目中说了5050个数中有2361个是不能整除的，我们可以拿来验证一下。
我们应该一眼就看到是计算了前100行。没看出来的话，可能还不如个小学生。传言高斯9岁时，老师刚讲完题，高斯的答案就出来了。这就是从1加到100等于5050的故事。
>>> n = 0
>>> result = 0
>>> for row in triangles():
... not_divisible = [x % 7> 0 for x in row]
... result = result + sum(not_divisible)
... n = n + 1
... if n == 100:
... break
...
>>> print(result)
2361
答案果然是对的。
不能总是暴力出奇迹
100行瞬间就出来了，但十亿行，光十亿个数就挺耗内存，再十亿行这么迭代下来，一个简单的任务，跑半天出不来结果。而PE的题都是要求1分钟内出结果的。显然我们又该拿出小学的本领了，看一组数字，看有没有规律（是不是学数列的时候，经常干这事）？
n = 0
result = 0
for row in triangles():
not_divisible = [x % 7> 0 for x in row]
result = result + sum(not_divisible)
if (n % 7 == 6):
end = "\n"
else:
end = "\t"
print(sum(not_divisible), end = end)
n = n + 1
if n == 100:
break
前面的代码，我们修改一下，把杨辉三角每一行不能整除7的数字打印出来。我看了数字之后，就发现规律了。我为了让你更容易看，把输出格式化一下，每7行写成一行，输出如下，规律明显：
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
开始真正的解题🔑
def int2(n, base):
ret = []
while n != 0:
n, k = n // base, n % base
ret.insert(0, k)
return ret
def PA(q, p):
return pow(28, p) * q * (q+1) /2
def factor(Q):
res = [1]
n = 0
for i in Q:
x = i + 1
res.append(x * res[n])
n = n + 1
res.pop()
return res
def count_nondivisible(N):
Q = int2(N, 7)
P = list(reversed(range(len(Q))))
items = [f*PA(q, p) for q, p, f in zip(Q, P, factor(Q))]
return sum(items)
首先检验一下，100行是不是2361.
>>> count_nondivisible(100)
2361.0
然后我们数一下十亿行的，答案是：
>>> count_nondivisible(pow(10, 9))
2129970655314432.0