PE 233 Lattice points on a circle (数论：毕格拉斯三元组（勾股数）)

ゝ一世哀愁。 2022-07-13 05:29 142阅读 0赞

Lattice points on a circle  
Problem 233  
Let f(N) be the number of points with integer coordinates that are on a circle passing through (0,0), (N,0),(0,N), and (N,N).  
It can be shown that f(10000) = 36.  
What is the sum of all positive integers N ≤ 10^11 such that f(N) = 420 ?

题意：  
圆周上的格点

作过点 ( 0 , 0 ) 、 ( N , 0 ) 、 ( 0 , N ) 和 ( N , N ) (0,0)、(N,0)、(0,N)和(N,N) (0,0)、(N,0)、(0,N)和(N,N)的圆，记圆周上坐标为整数的点的数目为 f ( N ) f(N) f(N)。

可以看出 f ( 10000 )   =   36 f(10000) = 36 f(10000) = 36。有些正整数 N   ≤   1 0 11 N ≤ 10^\{11\} N ≤ 1011且 f ( N )   =   420 f(N) = 420 f(N) = 420，这些正整数的和是多少？

题解：

这道题…额…70%的难度，难度比较高了…想了一天才想出来…唉…

一开始我就把方程化成： ( x − N / 2 ) 2 + ( y − N / 2 ) 2 = N 2 / 2 (x-N/2)^2+(y-N/2)^2=N^2/2 (x−N/2)2\+(y−N/2)2=N2/2 ==> ( 2 x − N ) 2 + ( 2 y − N ) 2 = 2 N 2 (2x-N)^2+(2y-N)^2=2N^2 (2x−N)2\+(2y−N)2=2N2。

这时发现当 N N N是奇数时，上面方程的左边就是 2 2 2个奇数的和，那么右边就是  2 m o d ( 4 ) 2 mod(4) 2mod(4)。

所以这说明所有 2 N 2 2N^2 2N2都可以表示为 2 2 2个奇数的平方之和。继续往这方向想就对了!

其实，当你计算 f ( 2 N ) : ( 0 , 0 ) ( 2 N , 0 ) ( 2 N , 2 N ) ( 0 , 2 N ) f(2N):(0,0) (2N, 0) (2N,2N) (0,2N) f(2N):(0,0)(2N,0)(2N,2N)(0,2N)时，这个就等同于计算 f ( N ) f(N) f(N)？（How to prove it?）

从上面的方程，我们就是求 （ x , y , N ） （x,y,N） （x,y,N）。因为N是奇数。假设 N = 5 N=5 N=5，那么我们在这个圆作一条 y = x y=x y=x的直线，很明显，  
 ( x , y ) = (x,y)= (x,y)= ( 3 , 4 ) (3,4) (3,4)是在这个圆上的，同理 ( 4 , 3 ) (4,3) (4,3)也在圆上。我猜这就是毕格拉斯三元组(其实就是)： x 2 + y 2 = N 2 x^2+y^2=N^2 x2\+y2=N2。然后可以  
计算出 f ( 5 ) = 12 。 f(5)=12。 f(5)=12。  
 12 12 12个： ( 4 , 3 ) , ( 3 , 4 ) , ( − 3 , 4 ) , ( 3 , − 4 ) , ( − 4 , 3 ) , ( 4 , − 3 ) , ( − 3 , − 4 ) , ( − 4 , − 3 ) , ( 0 , 5 ) , ( 5 , 0 ) , ( − 5 , 0 ) , ( 0 , − 5 ) 。 (4,3),(3,4),(-3,4),(3,-4),(-4,3),(4,-3),(-3,-4),(-4,-3),(0,5),(5,0),(-5,0),(0,-5)。 (4,3),(3,4),(−3,4),(3,−4),(−4,3),(4,−3),(−3,−4),(−4,−3),(0,5),(5,0),(−5,0),(0,−5)。

同样对于： f ( N ) = 420 f(N) = 420 f(N)=420。求 N N N。这里有 52 52 52个毕格拉斯三元组。 ( 52 ∗ 8 + 4 = 420 ) 。 (52 \* 8 + 4 = 420)。 (52∗8\+4=420)。

然后怎么求 N N N？

你可从这里得到解题思路：[http://mathworld.wolfram.com/PythagoreanTriple.html][http_mathworld.wolfram.com_PythagoreanTriple.html]

420 = 8 ∗ 52 + 4 。 420 = 8\*52+4。 420=8∗52\+4。  
 52 ∗ 2 + 1 = 105 = 3 ∗ 5 ∗ 7 = 3 ∗ 35 = 5 ∗ 21 = 7 ∗ 15 。 52\*2+1 = 105 = 3\*5\*7 = 3\*35 = 5\*21 = 7\*15。 52∗2\+1=105=3∗5∗7=3∗35=5∗21=7∗15。

如果( P i P\_i Pi是个素数） P i m o d ( 4 ) = 1 , 和 N = ( P 1 K 1 ∗ P 2 K 2 ∗ . . . ∗ P m K m ) ∗ r 。 P\_i mod(4)=1,和 N = (P\_1^K1 \*P\_2^K2\*...\*P\_m^Km)\*r。 Pimod(4)=1,和N=(P1K1∗P2K2∗...∗PmKm)∗r。  
然后 f ( N ) = 4 ∗ ( 2 ∗ K 1 + 1 ) ∗ ( 2 ∗ K 2 + 1 ) ∗ . . . ( 2 ∗ K m + 1 ) f(N) = 4\*(2\*K1+1)\*(2\*K2+1)\*...(2\*Km+1) f(N)=4∗(2∗K1\+1)∗(2∗K2\+1)∗...(2∗Km\+1)  
验证 f ( 10000 ) = 36 f(10000)=36 f(10000)=36,可以试试： K 1 = 1 , K 2 = 1 和 K 1 = 4 。 \{ K1=1,K2=1\}和 \{ K1=4 \}。 K1=1,K2=1和K1=4。  
 10000 = 5 ∗ 5 ∗ r , 10000=5\*5\*r, 10000=5∗5∗r,此时 r = 400.... r=400.... r=400....依次类推…  
注意：对于 f ( N ) = C , N f(N)=C, N f(N)=C,N不是唯一的！  
对于  f ( N ) = 420 f(N) = 420 f(N)=420 ,可以试试： K 1 = 1 , K 2 = 2 , K 3 = 3 \{K1 = 1 ,K2 = 2, K3 =3\} K1=1,K2=2,K3=3 和  K 1 = 2 , K 2 = 10 \{K1 = 2,K2 = 10\} K1=2,K2=10 和$ \{K1 = 3,K2 = 7\}$  
 420 = 4 ∗ 3 ∗ 5 ∗ 7 = 4 ∗ 5 ∗ 21 = 4 ∗ 7 ∗ 15 。 所 以 f ( n ) 420=4\*3\*5\*7=4\*5\*21=4\*7\*15。所以f(n) 420=4∗3∗5∗7=4∗5∗21=4∗7∗15。所以f(n)成立.

然后自己写代码求N吧…最后写出了正确的结果…再去看论坛,唉,自己太菜了…

[http_mathworld.wolfram.com_PythagoreanTriple.html]: http://mathworld.wolfram.com/PythagoreanTriple.html