0223 近勾股数一
* * * *
拉格朗日计划
* * * *
近勾股数一

若正整数$a,b,c$满足$a^2 + b^2 = c^2 + 1$,就称其为近勾股数。

有多少组满足$a\le b\le c$且$a+b+c$不超过两千五百万的近勾股数?

本题难度:



解答

若$(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