不能被除了1以外的任何完全平方数整除的数称为无平方因子数。

众所周知，二项式系数（即组合数）$\binom{n}{k}$可以如下排成三角形，称为帕斯卡三角形： $$ \begin{matrix} 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 \\ \end{matrix} $$ 可以看出帕斯卡三角形的前八行中共有十二个互不相同的数：1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35。

其中除4和20外都是无平方因子数，这些无平方因子数之和为105。

求帕斯卡三角形前51行所有不同的无平方因子数之和。

本题难度:

解答

小于50的素数共有15个：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47。

前51行中的无平方因子数只可能是这些素数的组合，共有$2^{15}=32768$个，计算出所有这些数，放入一个集合。

前51行中最大的数是$\binom{50}{25}$，用标准库完全可以计算，因此遍历所有这些组合数，逐一检查是否在上述集合中，去重后汇总即得$34029210557338$。

注：以下代码为Python3，因math.prod和math.comb均为Python3的新增函数。

import math,itertools

p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

sf=set([math.prod(c) for k in range(1,15) for c in itertools.combinations(p,k)])

print(1+sum(set([math.comb(n,k) for n in range(2,51) for k in range(1,n//2+1) if math.comb(n,k) in sf])))