0075 唯一勾股数和
* * * *
拉格朗日计划
* * * *
唯一勾股数和

考虑将一根电线弯折成边长均为整数的直角三角形,若折法唯一(即按升序排列边长a,b,c所得的三元数组是唯一的),则电线的最短长度是12。

当然,还有其它长度的电线也只能以唯一的方式弯折成边长均为整数的直角三角形,例如: \begin{align*} 12&=3+4+5, \\ 24&=6+8+10, \\ 30&=5+12+13, \\ 36&=9+12+15, \\ 40&=8+15+17, \\ 48&=12+16+20. \end{align*} 相反地,有些长度的电线,比如20,无法弯折成任何边长均为整数的直角三角形,而另一些长度的电线则有多种折法,例如, $$120=30+40+50=20+48+52=24+45+51.$$ 长度不超过一百五十万的电线中有多少种电线长度只能以唯一方式弯折成边长均为整数直角三角形?

本题难度:



解答

用欧几里得法生成所有的本原勾股数组,再缩放生成一百五十万以内的勾股数组,最后记录每个周长出现的频次即可。结果是$161667$。

target=750000
d={}

for m in range(2,900):
    for n in range(1,m):
        p=m*m+m*n
        a,b,c=sorted([m*m-n*n,2*m*n,m*m+n*n])
        i=1
        while i*p<=target:
            if i*p in d:
                d[i*p].add((i*a,i*b,i*c))
            else:
                d[i*p]=set([(i*a,i*b,i*c)])
            i+=1

print sum(len(d[p])==1 for p in d)