※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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).