プロジェクトオイラー問44 Problem 44 「五角数」 †

Problem 44 「五角数」 †

五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

である.

P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 - 22 = 48 は五角数ではない.

五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ.

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





解法
http://d.hatena.ne.jp/inamori/20100214/p2
いつまでたっても計算が終わらないのでこちらのサイトを参考にした。
式を立てて素因数を左辺と右辺に分配してリンク先式の逆行列が自然数になりかつ
2*Ｐｋ-n(3*n-1)/2が5角数ならそれが答えと判定。




is_pentagonal(N):-
      X is (1+sqrt(1+24*N))/6.0,
      X=:=floor(X).

div_list(N,D,BaseD,[D],N):-N mod BaseD>0,!.
div_list(N,D,BaseD,[D|ReD],ReN):-
      !,
      D1 is D*BaseD,
      N1 is N//BaseD,
      div_list(N1,D1,BaseD,ReD,ReN).

yakusu(1,_,[]):-!.
yakusu(N,D,[[1,N]]):-
      N<D*D,
      !.
yakusu(N,D,[Rs|Result]):-
      N mod D=:=0,
      !,
      div_list(N,1,D,Rs,N1),
      D1 is D+1,
      yakusu(N1,D1,Result).
yakusu(N,D,Result):-
      !,
      D1 is D+1,
      yakusu(N,D1,Result).
yakusu_distribution([],1,1):-!.
yakusu_distribution([L|List],X1,Y1):-
      reverse(L,[Top|_]),
      !,
      member(D1,L),
      D2 is Top//D1,
      yakusu_distribution(List,X,Y),
      X1 is X*D1,
      Y1 is Y*D2.

loopN(N):-
      NR is N*3-1,
      yakusu(N,2,List),
      yakusu(NR,2,List1),
      append(List,List1,List2),
      yakusu_distribution(List2,X,Y),
      Y1 is Y+1,
      A1 is 3*X+Y1,
      B1 is -3*X+Y1,
        A1>0,
      B1>0,
      A1 mod 6=:=0,
      B1 mod 6=:=0,
      B1<A1,
      Ans is (N*(3*N-1))//2,
      A2 is A1//6,
      B2 is B1//6,
      P1 is (A2*(3*A2-1))-Ans,
      is_pentagonal(P1),
      !,
      write([k,A2,j,B2,d,Ans]).
loopN(N):-
      !,
      N1 is N+1,
      loopN(N1).
main44:-
      loopN(1).