「プロジェクトオイラー問１２０」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問１２０」(2014/03/08 (土) 05:12:28) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
Problem 120 「自乗で割った余り」 †
(a-1)＾n+(a+1)＾n を a＾2 で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 6＾3 + 8＾3 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≤ a ≤ 1000 において, Σ rmax を求めよ.
解法
ｎ乗を展開してa^2で割ると残るのはnが奇数なら末尾のan+1とan-1
偶数なら1+1だけです。
奇数の時だけ考えて
an+1とan-1を足すと２anとなります
ｎは奇数なのでｎが増加すると
2a,6a,10a,,,と増加します。
a^2-2を4で割った余りが1か３なら2anはa(a-1)を作れます。
そうでないなら2anはa(a-2)を作れます。
後はこの場合わけを実装するだけです。
type(N,N1):-R is (N-2) mod 4,member(R,[1,3]),!,N1 is N-1.
type(N,N1):-!,N1 is N-2.
search(1001,Ans):-!,write(Ans).
search(N,Ans):-
!,
type(N,N1),
Add is N*N1,
Ans1 is Ans+Add,
N11 is N+1,
search(N11,Ans1).
main120:-
search(3,0).
Problem 120 「自乗で割った余り」 †
(a-1)＾n+(a+1)＾n を a＾2 で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 6＾3 + 8＾3 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≤ a ≤ 1000 において, Σ rmax を求めよ.
解法
ｎ乗を展開してa^2で割ると残るのはnが奇数なら末尾のan+1とan-1
偶数なら1+1だけです。
奇数の時だけ考えて
an+1とan-1を足すと２anとなります
ｎは奇数なのでｎが増加すると
2a,6a,10a,,,と増加します。
a^2-2を4で割った余りが1か３なら2anはa(a-1)を作れます。
そうでないなら2anはa(a-2)を作れます。
後はこの場合わけを実装するだけです。
この解放は海外のプロジェクトオイラー解説サイトの方法を参考に少し処理を改善して記述しました。
type(N,N1):-R is (N-2) mod 4,member(R,[1,3]),!,N1 is N-1.
type(N,N1):-!,N1 is N-2.
search(1001,Ans):-!,write(Ans).
search(N,Ans):-
!,
type(N,N1),
Add is N*N1,
Ans1 is Ans+Add,
N11 is N+1,
search(N11,Ans1).
main120:-
search(3,0).
