「プロジェクトオイラー問２６」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問２６ - (2014/02/14 (金) 04:53:14) のソース

http://projecteuler.net/problem=26

*Problem 26 「逆数の循環節 その1」 †
単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.



解法
オイラーのファイ関数によれば
1/pが循環するということはフェルマーの小定理によれば必ず10^φ(p) mod P=1となるということです。
条件式を10^r mod P=1とすれば
オイラーのファイ関数 fai(p)の約数のなかで条件式を満たす最小値が答えとなります。
これを探します。



 modPow(_,0,Result,_,Result):-!.
 modPow(P,R,Mult,Pow10,Result):-
 	R mod 2=:=1,
 	!,
 	R1 is R//2,
 	Mult1 is (Mult*Pow10) mod P,
 	Pow10_1 is (Pow10^2) mod P,
 	modPow(P,R1,Mult1,Pow10_1,Result).
 modPow(P,R,Mult,Pow10,Result):-
 	!,
 	R1 is R//2,
 	Pow10_1 is Pow10^2,
 	modPow(P,R1,Mult,Pow10_1,Result).
 
 min(A,B,A):-A<B,!.
 min(_,B,B):-!.
 min_search([X],X):-!.
 min_search([X|Xs],Result):-
 	min_search(Xs,Re),
 	min(X,Re,Result). 
 yakusu(N,P,P):-N mod P=:=0.
 yakusu(N,P,P1):-N>P*P,N mod P=:=0,!,P1 is N//P.
 
 ok_yakusu_list(N,R):-
 	NM is N-1,
  	between(1,NM,Div),
 	Div2 is Div^2,
	(NM < Div2 ->!,fail;true),
  	yakusu(NM,Div,R),
 	modPow(N,R,1,10,Amari),
 	Amari=:=1.
 max_yakusu([MinY,N]):-
 	between(2,999,N),
  	findall(Y,ok_yakusu_list(N,Y),Ys),
 	min_search(Ys,MinY).
 main26:-
 	findall(X,max_yakusu(X),Xs),
 	sort(Xs,Xs1),
 	write(Xs1).