「プロジェクトオイラー問130」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問130」の最新版変更点

追加された行は青色になります。

削除された行は赤色になります。

 *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の9倍は
 (10^t)-1=999,,,999と表現できます。
 (10^t) mod N*9=1
 となれば
 ((10^t)-1)/9=111,,,111はnで割り切れます。
 tはオイラーの定理よりφ(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).