|
|
!ピタゴラス数
!
!問題
!自然数m,nが
! 0<n<m、m,nのどちらかは偶数である、(m,n)=1（m,nは互いに素）
!を満たすとき、
!既約なピタゴラス数(a,b,c)は、(m^2-n^2, 2*m*n, m^2+n^2)で求まる。
!
!a≦b≦cとして、aの小さい順に求めよ。
!
!答え
!c-a=(m^2+n^2)-(m^2-n^2)=2*n^2>0、c-b=(m^2+n^2)-(2*m*n)=(m-n)^2>0より、
!a,bは直角を挟む2辺、cを斜辺となる。
!aとbの大小関係はここでは未定として、
!a=m^2-n^2（奇数）、a=2*m*n（偶数）に場合分けして対応する。
!a=m^2-n^2のとき
! a=m^2-n^2=(m-n)*(m+n)から、aを2つの因数s,t（s<t）に分解する。
! s=m-n、t=m+nより、b,cをs,tで表すと
! b=2*m*n={(m+n)^2-(m-n)^2}/2=(t^2-s^2)/2
! c=m^2+n^2={(m+n)^2+(m-n)^2}/2=(t^2+s^2)/2
!a=2*m*nのとき
! a/2=m*nから、aを2つの因数m,nに分解する。
FOR a=1 TO 100 !aの小さい順
IF MOD(a,2)=1 THEN !奇数なら
FOR s=INT(SQR(a)) TO 1 STEP -1 !aを2つの因数s,tに分解する
LET t=a/s
IF t=INT(t) AND s<t THEN
LET b=(t^2-s^2)/2 !bを求める
IF b=INT(b) AND a<=b THEN
LET c=(t^2+s^2)/2 !cを求める
IF c=INT(c) AND b<=c THEN
IF gcd3(a,b,c)=1 THEN PRINT a;b;c !解を表示する
END IF
END IF
END IF
NEXT s
ELSE !偶数なら
LET a2=a/2
FOR n=INT(SQR(a2)) TO 1 STEP -1 !aを2つの因数m,nに分解する
LET m=a2/n
IF m=INT(m) AND n<m THEN
LET b=(m^2-n^2) !bを求める
IF b=INT(b) AND a<=b THEN
LET c=(m^2+n^2) !cを求める
IF c=INT(c) AND b<=c THEN
IF gcd3(a,b,c)=1 THEN PRINT a;b;c !解を表示する
END IF
END IF
END IF
NEXT n
END IF
NEXT a
END
EXTERNAL FUNCTION gcd3(a,b,c) !最大公約数
LET gcd3=gcd(gcd(a,b),c)
END FUNCTION
EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET gcd=a
END FUNCTION
|
|