若$(a,b,c)$是一组近勾股数,则以下三组映射所得的也都是近勾股数:
$$
\begin{pmatrix}a \\ b \\ c\end{pmatrix}\mapsto\begin{pmatrix}1 & -2 & 2 \\ 2 & -1 & 2 \\ 2 & -2 & 3 \end{pmatrix} \begin{pmatrix}a \\ b \\ c\end{pmatrix}, \quad
\begin{pmatrix}a \\ b \\ c\end{pmatrix}\mapsto\begin{pmatrix}2 & 1 & 2 \\ 1 & 2 & 2 \\ 2 & 2 & 3 \end{pmatrix} \begin{pmatrix}a \\ b \\ c\end{pmatrix}, \quad
\begin{pmatrix}a \\ b \\ c\end{pmatrix}\mapsto\begin{pmatrix}-2 & 1 & 2 \\ -1 & 2 & 2 \\ -2 & 2 & 3 \end{pmatrix} \begin{pmatrix}a \\ b \\ c\end{pmatrix}.
$$
这是因为
\begin{align*}
(a-2b+2c)^2+(2a-b+2c)^2-(2a-2b+3c)^2&=a^2+b^2-c^2=1, \\
(2a+b+2c)^2+(a+2b+2c)^2-(2a+2b+3c)^2&=a^2+b^2-c^2=1, \\
(-2a+b+2c)^2+(-a+2b+2c)^2-(-2a+2b+3c)^2&=a^2+b^2-c^2=1.
\end{align*}
若$a=b$,则第一组和第三组映射的结果相同,其他情况所得的数组均不同,且所有的近勾股数均可由初值$(1,1,1)$和$(2,2,2)$生成。
遍历搜索后即得结果$61614848$,为节省内存,此处使用的是深度优先搜索。
注:本题的构造来自于所谓的本原勾股数组树。
注2:因搜索范围较大,以下代码中打印了进度信息。
def A(x,y,z):
return x-2*y+2*z, 2*x-y+2*z, 2*x-2*y+3*z
def B(x,y,z):
return 2*x+y+2*z, x+2*y+2*z, 2*x+2*y+3*z
def C(x,y,z):
return -2*x+y+2*z, -x+2*y+2*z, -2*x+2*y+3*z
bound=25000000
r=0
h=[(1,1,1),(1,2,2)]
while h:
a,b,c=h.pop()
r+=1
u,v,w=A(a,b,c)
if u+v+w<=bound:
h.append((u,v,w))
r+=1
u,v,w=B(a,b,c)
if u+v+w<=bound:
h.append((u,v,w))
r+=1
if a!=b:
u,v,w=C(a,b,c)
if u+v+w<=bound:
h.append((u,v,w))
r+=1
if r%1000000==0:
print i/1000000,"million triples checked"
print r
|