题目142：完全平方数集合

欧拉计划

Perfect Square Collection

Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x − y, x + z, x − z, y + z, y − z are all perfect squares.

题目：

求满足  x + y， x − y，x + z，x − z，y + z，y − z 都是完全平方数，并且 x > y > z > 0 的最小的 x + y + z。

jerryxjr1220

先用代数转换：
x+y=a
x-y=b
x+z=c
x-z=d
y+z=e
y-z=f

x=(a+b)/2
y=(a-b)/2
z=c-x=c-(a+b)/2
d=x-z=(a+b)/2-c+(a+b)/2=a+b-c
e=y+z=(a-b)/2+c-(a+b)/2=c-b
f=y-z=(a-b)/2-c+(a+b)/2=a-c

由于a，b，c都是完全平方数，即可表示为a*a，b*b，c*c，同理求得d，e，f和x，y，z

用numba加速

from numba import jit
@jit
def p142():
        for a in range(3, 10000000):
                for c in range(2, a):
                        for b in range(1, c):
                                x = (a*a+b*b)/2
                                y = (a*a-b*b)/2
                                z = c*c-(a*a+b*b)/2
                                d = a*a+b*b-c*c
                                e = c*c-b*b
                                f = a*a-c*c
                                if int(d**0.5)**2 == d and int(e**0.5)**2 == e and int(f**0.5)**2 == f and x % 1 == 0 and y % 1 == 0 and z % 1 == 0 and z>0:
                                        return x+y+z
print(p142())

1006193.0
[Finished in 4.0s]