COdeIQ:「ツイン・トライアングル」問題の解答


Kawazoe(@riverplus)さんのCodeIQの問題です。
問題はこちらの御世話になりました。解答例もあります。
~~->https://blog.goo.ne.jp/r-de-r/e/45659ad975496af9b1b7de04a8d2305d
->https://blog.goo.ne.jp/r-de-r/e/44e77fc0784eef7457ffdd88c8771609~~
(リンク切れしていました2025.5.2)
URLが変わっていましたがありました。（2025.5.3追加）
->https://sangaku0418.hatenablog.com/entry/2015/11/16/172931
->https://sangaku0418.hatenablog.com/entry/2015/12/04/100100

ーーー2025.5.2追加
自然数a,bを直角を挟む二辺とする直角三角形の外接円の外接三角形のうち、
元の三角形と相似で、直角を挟む辺が自然数のもののかずを求める問題です。
但しa<=b<=Lのすべてのa,bに対して該当するものの和を求めます。
ーーー

こちらにも情報があります。
->https://posfie.com/@riverplus/p/SeiCU5C

求める外接三角形の辺の長さは原始ピタゴラス数の整数倍です。
原始ピタゴラス数は3つの数が互いに素（ある2数が互いに素)なピタゴラス数です。
さらに整数辺の直角三角形の公式(a,b,c)=(I^2-J^2,2\*I\*J,I^2+J^2)(aが奇数)と、
三辺が(a1,b1,c1)の外接直角三角形の斜辺が、内接円の半径をrとしますと、
c1=a1-r+b1-r=a1+b1-c　(2*r=c)をとなるのを利用します。
この時I,Jは互いに素かつI>Jとなります。

Prologです。
c^2=I^2+J^2<=2\*L^2よりI<=√(L/√(2))
先ずloop1/6で1からNまで互いに素でない2数、a,b>Lとなる数、偶数のaを除き、
loop2/6で原始ピタゴラス数をk倍した数が題意を満たすかどうか調べます。
すなわち外接三角形の面積の倍 (a1+b1+(a1+b1-2*r))\*r=a1\*b1 を変形して
a1=r\*(a+b+r)/(2\*b),b1=r\*(a+b+r)/(2\*a)が整数なら返り値を1増やします。

```Prolog
%SWI-Prolog ver 7.42,7.64,9.25
%:-initialization(start).       %Online Prolog Compiler,ideone.    
%start.

loop2(0,_,_,_,R,R).
loop2(K,X,Y,Z,R1,R):-
   X1 is X*K,Y1 is Y*K,Z1 is Z*K,V is (X1 + Y1 + Z1) * Z1,
   ((mod(V,X1*2)=:=0,mod(V,Y1*2)=:=0)->R2 is R1+1;R2 = R1),
   K1 is K-1,loop2(K1,X,Y,Z,R2,R).
   
loop1(N0,N,I,_,R,R):-
   N<I,!.
loop1(N0,N,I,J,R1,R):-
   J =:= I,!,I1 is I+1,loop1(N0,N,I1,1,R1,R).
loop1(N0,N,I,J,R1,R):-
   gcd(I,J)=\=1,!,J1 is J+1,loop1(N0,N,I,J1,R1,R).
loop1(N0,N,I,J,R1,R):-
   X0 is I^2-J^2,J1 is J+1,((0=:=mod(X0,2);X0>N0)->loop1(N0,N,I,J1,R1,R);
  (Y0 is 2*I*J,(Y0>N0->(I1 is I+1,loop1(N0,N,I1,1,R1,R));
  (Z0 is I^2+J^2,K is min(div(N0,X0),div(N0,Y0)),loop2(K,X0,Y0,Z0,R1,R2),
   loop1(N0,N,I,J1,R2,R))))).

solve(N0,R):-N is floor(sqrt(N0/sqrt(2))),loop1(N0,N,2,1,0,R).

start:-
    f(N0,A),(solve(N0,R)->(R==A->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(N0->R),fail.
start.

f(10,1).
f(50,7).
f(100,15).
f(456,77).
f(1000, 173).      %抜けていたので追加（2025.4.5）
f(7654,1405).
f(75319,14133).
f(90346,16972).
f(100000,18797).
```
以前juliaで解いていたのですが、投稿しようとして見直したときに、
自分でも何をしているのかわかりませんでした。
そこで新たにプログラムを書きましたが、
元のほうがやや速いようですのでもう一度考えてみました。

求める外接三角形の辺の長さは原始ピタゴラス数の整数倍ですが、
原始ピタゴラス数とその奇数倍のピタゴラス数では
a,cが奇数、bが偶数ですので、a\*cは奇数,a+b-cは偶数となり
a*c/(a+b-c)が整数となりませんので、題意に会う外接三角形はありません。

a<bの場合を除外するとa<bとなる原始ピタゴラス数が除かれますが、
原始ピタゴラス数の二倍のピタゴラス数（2\*a,2\*b,2\*c）があるとすれば
2*(i^2-j^2)=(h＊i)^2-(2\*j/h)^2からhを求めるとh=√2。これはあり得ません。
一方
2\*b=2\*2\*i\*j=(i+j)^2-(i-j)^2,2\*a=2\*(i^2-j^2)=2\*(i+j)(i-j),
2\*b>2\*aなので、ピタゴラス数(2\*b,2\*a,2\*c)が求められます。
ただしI<=√(L/√(2))のときi1=i+jとするとi<=Iなのでi1<=2*Iです。

またa1/a=b1/b=(a1+b1-c)/cからa1=a\*c/(a+b-c),b1=b\*c/(a+b-c)となります。

よってi<=n,j<iとなるi,jで、
i,jが互いに素でない場合,a>Lの場合,a<bの場合を除外し、
(a,b,c)のk倍の(a1,b1,c1)に関してa1\*c1/(a1+b1-c1),b1\*c1/(a1+b1-c1)
が整数なら返り値に1を足します。

```Julia
#julia ver 1.41,1.53,1.10.3

function solve(n0,v)
    n = Int(floor(sqrt(sqrt(2)*n0))) 
    sum = 0
    for i in 2 : n
     for j in 1 : i-1
       if gcd(i,j) !=  1 
          continue　　　
       end
       a = i^2 - j^2　　
       if a>n0 　　　　　
          continue
       end
       b = 2*i*j
       if b>a  
         break
       end
       c = i^2 + j^2
       for k in 1 : div(n0,a)
         a1 = a*k
         b1  =b*k
         c1 = c*k
         am = rem(a1*c1, a1+b1-c1)  
         bm = rem(b1*c1, a1+b1-c1)　
         if am == 0 && bm == 0
           sum+=1
         end
        end
      end
    end
     s = v == sum ? "ok " : "no "
     println(s,n0,"->",sum)
end

solve(10, 1)
solve(50, 7)
solve(100, 15)
solve(456, 77)
solve(1000, 173)
solve(7654, 1405)
solve(75319, 14133)
solve(90346, 16972)
solve(100000, 18797)
```