プロジェクトオイラー Problem 57 「平方根の近似分数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2057

Problem 57 「平方根の近似分数」 †

2の平方根は無限に続く連分数で表すことができる.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

最初の4回の繰り返しを展開すると以下が得られる.

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?

解法
定義通り計算するだけ。

gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).

calc(_,_,1001,_):-!,fail.
calc(U,D,_,1):-
      U1 is U+D,
      D1 is D,
      gcd(U1,D1,G1),
      U2 is U1//G1,
      D2 is D1//G1,
      number_codes(U2,L1),
      number_codes(D2,L2),
      length(L1,Len1),
      length(L2,Len2),
      Len1>Len2.
calc(U,D,Deep,Result):-
      !,
      U1 is U+D*2,
      D1 is D,
      gcd(U1,D1,G1),
      U2 is U1//G1,
      D2 is D1//G1,
      Deep1 is Deep+1,
      calc(D2,U2,Deep1,Result).
main57:-findall(E,calc(1,2,1,E),All),
      length(All,Ans),
      write(Ans).