Pierpont primes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added/changed whitespace and comments, simplified program.) |
|||
Line 1,442: | Line 1,442: | ||
end function</lang> |
end function</lang> |
||
=={{header|Prolog}}== |
|||
<lang Prolog> |
|||
?- use_module(library(heaps)). |
|||
three_smooth(Lz) :- |
|||
singleton_heap(H, 1, nothing), |
|||
lazy_list(next_3smooth, 0-H, Lz). |
|||
next_3smooth(Top-H0, N-H2, N) :- |
|||
min_of_heap(H0, Top, _), !, |
|||
get_from_heap(H0, Top, _, H1), |
|||
next_3smooth(Top-H1, N-H2, N). |
|||
next_3smooth(_-H0, N-H3, N) :- |
|||
get_from_heap(H0, N, _, H1), |
|||
N2 is N * 2, |
|||
N3 is N * 3, |
|||
add_to_heap(H1, N2, nothing, H2), |
|||
add_to_heap(H2, N3, nothing, H3). |
|||
first_kind(K) :- |
|||
three_smooth(Ns), member(N, Ns), |
|||
K is N + 1, |
|||
prime(K). |
|||
second_kind(K) :- |
|||
three_smooth(Ns), member(N, Ns), |
|||
K is N - 1, |
|||
prime(K). |
|||
show(Seq, N) :- |
|||
format("The first ~w values of ~s are: ", [N, Seq]), |
|||
once(findnsols(N, X, call(Seq, X), L)), |
|||
write(L), nl, |
|||
once(offset(249, call(Seq, TwoFifty))), |
|||
format("The 250th value of ~w is ~w~n", [Seq, TwoFifty]). |
|||
main :- |
|||
show(first_kind, 50), nl, |
|||
show(second_kind, 50), nl, |
|||
halt. |
|||
% primality checker -- Miller Rabin preceded with a round of trial divisions. |
|||
prime(N) :- |
|||
integer(N), |
|||
N > 1, |
|||
divcheck( |
|||
N, |
|||
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, |
|||
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, |
|||
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, |
|||
139, 149], |
|||
Result), |
|||
((Result = prime, !); miller_rabin_primality_test(N)). |
|||
divcheck(_, [], unknown) :- !. |
|||
divcheck(N, [P|_], prime) :- P*P > N, !. |
|||
divcheck(N, [P|Ps], State) :- N mod P =\= 0, divcheck(N, Ps, State). |
|||
miller_rabin_primality_test(N) :- |
|||
bases(Bases, N), |
|||
forall(member(A, Bases), strong_fermat_pseudoprime(N, A)). |
|||
miller_rabin_precision(16). |
|||
bases([31, 73], N) :- N < 9_080_191, !. |
|||
bases([2, 7, 61], N) :- N < 4_759_123_141, !. |
|||
bases([2, 325, 9_375, 28_178, 450_775, 9_780_504, 1_795_265_022], N) :- |
|||
N < 18_446_744_073_709_551_616, !. % 2^64 |
|||
bases(Bases, N) :- |
|||
miller_rabin_precision(T), RndLimit is N - 2, |
|||
length(Bases, T), maplist(random_between(2, RndLimit), Bases). |
|||
strong_fermat_pseudoprime(N, A) :- % miller-rabin strong pseudoprime test with base A. |
|||
succ(Pn, N), factor_2s(Pn, S, D), |
|||
X is powm(A, D, N), |
|||
((X =:= 1, !); \+ composite_witness(N, S, X)). |
|||
composite_witness(_, 0, _) :- !. |
|||
composite_witness(N, K, X) :- |
|||
X =\= N-1, |
|||
succ(Pk, K), X2 is (X*X) mod N, composite_witness(N, Pk, X2). |
|||
factor_2s(N, S, D) :- factor_2s(0, N, S, D). |
|||
factor_2s(S, D, S, D) :- D /\ 1 =\= 0, !. |
|||
factor_2s(S0, D0, S, D) :- |
|||
succ(S0, S1), D1 is D0 >> 1, |
|||
factor_2s(S1, D1, S, D). |
|||
?- main. |
|||
</lang> |
|||
{{Out}} |
|||
<pre> |
|||
The first 50 values of first_kind are: [2,3,5,7,13,17,19,37,73,97,109,163,193,257,433,487,577,769,1153,1297,1459,2593,2917,3457,3889,10369,12289,17497,18433,39367,52489,65537,139969,147457,209953,331777,472393,629857,746497,786433,839809,995329,1179649,1492993,1769473,1990657,2654209,5038849,5308417,8503057] |
|||
The 250th value of first_kind is 62518864539857068333550694039553 |
|||
The first 50 values of second_kind are: [2,3,5,7,11,17,23,31,47,53,71,107,127,191,383,431,647,863,971,1151,2591,4373,6143,6911,8191,8747,13121,15551,23327,27647,62207,73727,131071,139967,165887,294911,314927,442367,472391,497663,524287,786431,995327,1062881,2519423,10616831,17915903,18874367,25509167,30233087] |
|||
The 250th value of second_kind is 4111131172000956525894875083702271 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Go}} |
{{trans|Go}} |