プロジェクトオイラー Problem 53 「組み合わせ選択」 †

Problem 53 「組み合わせ選択」 †

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.

一般に, r ≤ n について nCr = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する.

n = 23 になるまで, これらの値が100万を超えることはない: 23C10 = 1144066.

1 ≤ n ≤ 100 について, 100万を超える nCr は何通りあるか?

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

解法
一段ずつ計算してみました。
他の方法としては。
各段で右端か左端から計算を初めて１００万を超えるところで計算を止めて。
ｎ段めならｎ-１００万になる直前までの幅*２で計算しても大した計算量にはならないのでそれもよいかと思います。


add(X,Y,Z):-Z is X+Y,Z<1000*1000,!.
add(_,_,1000000):-!.

next_row([X],[],[X]):-!.
next_row([X|Xs],[Y|Ys],[Z|Zs]):-
      !,
        add(X,Y,Z),
      next_row(Xs,Ys,Zs).

countMillion([],0):-!.
countMillion([X|Xs],Result):-
      X=:=1000*1000,
      !,
      countMillion(Xs,Re),
      Result is Re+1.
countMillion([_|Xs],Result):-
      !,
      countMillion(Xs,Result).

dp(_,101,Sum):-!,write(Sum).
dp(List,Row,Sum):-
      [_|List1]=List,
      next_row(List,List1,List2),
      List3=[1|List2],
      Row1 is Row+1,
      countMillion(List3,Add),
      Sum1 is Sum+Add,
      dp(List3,Row1,Sum1).

main53:-
      dp([1],1,0).