0142 平方数集
* * * *
拉格朗日计划
* * * *
平方数集

找出最小的$x+y+z$的值,其中x、y、z是递减的自然数,且$x\pm y$、$x\pm z$、$y\pm z$都是完全平方数。

本题难度:



解答

设 $$\begin{cases}x+z=r^2, \\ x+y=s^2, \\ y+z=t^2 \end{cases}$$ 则有 $$x=\frac{r^2-t^2+s^2}{2}, \quad y=\frac{s^2-r^2+t^2}{2}, \quad z=\frac{r^2-s^2+t^2}{2}.$$ 若令 $$\begin{cases}x-z=c^2, \\ x-y=b^2, \\ y-z=a^2, \end{cases},$$ 则可得 $$\begin{cases}s^2-t^2=c^2, \\ r^2-t^2=b^2, \\ s^2-r^2=a^2, \end{cases}$$ 即 $$\begin{cases}s^2=c^2+t^2, \\ r^2=b^2+t^2, \\ c^2=a^2+b^2, \end{cases}$$ 形成三组勾股数。

用欧几里得算法生成一定范围内的所有勾股数(需要尝试若干次以确定范围,实验显示取不超过1000的$c,r,s$足矣)。

枚举所有可能的组合并检验可得结果为$x=434657$, $y=420968$, $z=150568$,它们的和是$1006193$。

import math,itertools
q=set([i*i for i in range(1,1000)])
d=set([])
for m in range(2,32):
    for n in range(1-m%2,min(math.isqrt(1000000-m*m)+1,m),2):
        if math.gcd(m,n)==1:
            a,b,c=m*m-n*n,2*m*n,m*m+n*n
            if c < 1000:
                i=1
                while c*i < 1000:
                    d.add(c*i)
                    i+=1

def check(c,r,s):
    c2,r2,s2=c*c,r*r,s*s
    t2=s2-c2
    a2=s2-r2
    b2=c2-a2
    if (t2 in q) and (a2 in q) and (b2 in q) and (b2+t2==r2) and r2+t2>s2 and (s2+r2+t2)%2==0:
        return [(s2+r2+t2)//2,(r2-t2+s2)//2,(s2-r2+t2)//2,(r2-s2+t2)//2]
    else:
        return [99999999]*4

for c,r,s in itertools.combinations(sorted(list(d)),3):
    a,b=check(c,r,s),check(r,c,s)
    if a[0] < 99999999 or b[0] < 99999999:
        print(min(a,b))
        break