「プロジェクトオイラー問１３０」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問１３０」(2014/03/09 (日) 08:24:05) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」 †
1からのみなる数をレピュニットと呼ぶ. R(k)で長さkのレピュニットを表す. 例えばR(6) = 111111である.
GCD(n, 10) = 1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる. A(n) でそのような最小の k を表す. 例: A(7) = 6. A(41) = 5.
5より大きい素数 p について, A(p) が p - 1 を割り切ることが知られている. p = 41 のときには, A(41) = 5 であり, 40は5で割り切れる.
非常に少ないのだが, 合成数においても上が成立する場合がある. 最初の5つの例は 91, 259, 451, 481, 703 である.
GCD(n, 10) = 1 かつ A(n) が n - 1 を割り切るような最初の25個の合成数 n の総和を求めよ.
解法
1111、、、1111の９倍は
(10^t)-1=999,,,999と表現できます。
(10^t) mod N*9=1
となれば
((10^t)-1)/9=111,,,111はｎで割り切れます。
ｔはオイラーの定理よりφ(n)となります。
not_prime(N):-N<2,!.
not_prime(N):-
between(2,N,D),
(D*D>N->!,fail;true),
N mod D=:=0,
!.
is_prime(N):-not(not_prime(N)).
divs(N,Div,N):-N mod Div>0,!.
divs(N,Div,Result):-
!,
N1 is N//Div,
divs(N1,Div,Result).
fai(1,_,Result,Result):-!.
fai(N,Div,Re,Result):-
N<Div*Div,
!,
Result is (Re/N)*(N-1).
fai(N,Div,Mult,Result):-
N mod Div=:=0,
!,
divs(N,Div,N1),
Mult1 is (Mult/Div)*(Div-1),
Div1 is Div+1,
fai(N1,Div1,Mult1,Result).
fai(N,Div,Mult,Result):-
!,
Div1 is Div+1,
fai(N,Div1,Mult,Result).
fai_w(N,Result):-
!,
fai(N,2,N,Result).
calc10(_,0,_,Mult):-
!,
Mult=:=1.
calc10(N10,R,N,Mult):-
R mod 2=:=1,
!,
Mult1 is (Mult*N10) mod N,
N10_2 is (N10*N10) mod N,
R1 is R//2,
calc10(N10_2,R1,N,Mult1).
calc10(N10,R,N,Mult):-
!,
N10_2 is (N10*N10) mod N,
R1 is R//2,
calc10(N10_2,R1,N,Mult).
d1(_,D,D).
d1(Fai,D,Result):-Fai mod D=:=0,Result is Fai//D.
check1(N,D1):-
N mod 2>0,
N mod 5>0,
not_prime(N),
fai_w(N,Fai),
!,
between(2,Fai,D),
(Fai<D*D->!,fail;true),
d1(Fai,D,D1),
2<D1,
N1 is N*9,
calc10(10,D1,N1,1).
check(N):-
findall(D,check1(N,D),List),
sort(List,[Top|_]),
(N-1) mod Top=:=0,
!,
write([N,Top]).
search(_,Sum,25):-!,write([ans,Sum]).
search(N,Sum,Count):-
check(N),
!,
Sum1 is Sum+N,
N1 is N+1,
Count1 is Count+1,
search(N1,Sum1,Count1).
search(N,Sum,Count):-
!,
N1 is N+1,
search(N1,Sum,Count).
main130:-
search(2,0,0).
*Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」 †
1からのみなる数をレピュニットと呼ぶ. R(k)で長さkのレピュニットを表す. 例えばR(6) = 111111である.
GCD(n, 10) = 1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる. A(n) でそのような最小の k を表す. 例: A(7) = 6. A(41) = 5.
5より大きい素数 p について, A(p) が p - 1 を割り切ることが知られている. p = 41 のときには, A(41) = 5 であり, 40は5で割り切れる.
非常に少ないのだが, 合成数においても上が成立する場合がある. 最初の5つの例は 91, 259, 451, 481, 703 である.
GCD(n, 10) = 1 かつ A(n) が n - 1 を割り切るような最初の25個の合成数 n の総和を求めよ.
解法
1111、、、1111の９倍は
(10^t)-1=999,,,999と表現できます。
(10^t) mod N*9=1
となれば
((10^t)-1)/9=111,,,111はｎで割り切れます。
ｔはオイラーの定理よりφ(n)となります。
not_prime(N):-N<2,!.
not_prime(N):-
between(2,N,D),
(D*D>N->!,fail;true),
N mod D=:=0,
!.
is_prime(N):-not(not_prime(N)).
divs(N,Div,N):-N mod Div>0,!.
divs(N,Div,Result):-
!,
N1 is N//Div,
divs(N1,Div,Result).
fai(1,_,Result,Result):-!.
fai(N,Div,Re,Result):-
N<Div*Div,
!,
Result is (Re/N)*(N-1).
fai(N,Div,Mult,Result):-
N mod Div=:=0,
!,
divs(N,Div,N1),
Mult1 is (Mult/Div)*(Div-1),
Div1 is Div+1,
fai(N1,Div1,Mult1,Result).
fai(N,Div,Mult,Result):-
!,
Div1 is Div+1,
fai(N,Div1,Mult,Result).
fai_w(N,Result):-
!,
fai(N,2,N,Result).
calc10(_,0,_,Mult):-
!,
Mult=:=1.
calc10(N10,R,N,Mult):-
R mod 2=:=1,
!,
Mult1 is (Mult*N10) mod N,
N10_2 is (N10*N10) mod N,
R1 is R//2,
calc10(N10_2,R1,N,Mult1).
calc10(N10,R,N,Mult):-
!,
N10_2 is (N10*N10) mod N,
R1 is R//2,
calc10(N10_2,R1,N,Mult).
d1(_,D,D).
d1(Fai,D,Result):-Fai mod D=:=0,Result is Fai//D.
check1(N,D1):-
N mod 2>0,
N mod 5>0,
not_prime(N),
fai_w(N,Fai),
!,
between(2,Fai,D),
(Fai<D*D->!,fail;true),
d1(Fai,D,D1),
2<D1,
N1 is N*9,
calc10(10,D1,N1,1).
check(N):-
findall(D,check1(N,D),List),
sort(List,[Top|_]),
(N-1) mod Top=:=0,
!,
write([N,Top]).
search(_,Sum,25):-!,write([ans,Sum]).
search(N,Sum,Count):-
check(N),
!,
Sum1 is Sum+N,
N1 is N+1,
Count1 is Count+1,
search(N1,Sum1,Count1).
search(N,Sum,Count):-
!,
N1 is N+1,
search(N1,Sum,Count).
main130:-
search(2,0,0).
