AKS test for primes: Difference between revisions
Prolog
(Added zkl) |
(Prolog) |
||
Line 649:
<pre>Primes up to 100:
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</pre>
=={{header|Prolog}}==
===Prolog(ue)===
The AKS Theorem ties together two elementary concepts in mathematics:
prime numbers and the Pascal triangle. The simplicity of the
connection can be expressed directly in Prolog by the following prime number
generator:
<lang prolog>
prime(P) :-
pascal([1,P|Xs]),
append(Xs, [1], Rest),
forall( member(X,Xs), 0 is X mod P).
</lang>
where pascal/1 is a generator of rows of the Pascal triangle, for
example as defined below; the other predicates used above are
standard.
This solution to the Rosetta Code problems will accordingly focus on
the Pascal triangle, but to illustrate a number of points, we shall
exploit its symmetry by representing each of its rows by the longest
initial non-decreasing segment of that row, as illustrated in the
third column of the following table:
<pre>
Row Pascal Row optpascal
1 1 [1]
2 1 1 [1, 1]
3 1 2 1 [1, 2]
4 1 3 3 1 [1, 3, 3]
</pre>
We shall refer to this condensed representation of a row as an
"optpascal list". Using it, we can simplify and improve
the above prime number generator by defining it as follows:
prime(N) :- optpascal([1,N|Xs]), forall( member(X,Xs), 0 is X mod N).
Using SWI-Prolog without any modifying the default parameters, this
prime number generator was used to generate all primes up to and
including 75,659.
Since Pascal triangles are the foundation of our approach to
addressing the specific Rosetta Code problems, we being by defining
the generator pascal/2 that is required by the first problem, but we
do so by defining it in terms of an efficient generator, optpascal/1.
===Pascal Triangle Generator===
<lang prolog>
% To generate the n-th row of a Pascal triangle
% pascal(+N, Row)
pascal(0, [1]).
pascal(N, Row) :-
N > 0, optpascal( [1, N|Xs] ),
!,
pascalize( [1, N|Xs], Row ).
pascalize( Opt, Row ) :-
% if Opt ends in a pair, then peel off the pair:
( append(X, [R,R], Opt) -> true ; append(X, [R], Opt) ),
reverse(X, Rs),
append( Opt, Rs, Row ).
% optpascal(-X) generates optpascal lines:
optpascal(X) :-
optpascal_successor( [], X).
% optpascal_successor(+P, -Q) is true if Q is an optpascal list beneath the optpascal list P:
optpascal_successor(P, Q) :-
optpascal(P, NextP),
(Q = NextP ; optpascal_successor(NextP, Q)).
% optpascal(+Row, NextRow) is true if Row and NextRow are adjacent rows in the Pascal triangle.
% optpascal(+Row, NextRow) where the optpascal representation is used
optpascal(X, [1|Y]) :-
add_pairs(X, Y).
% add_pairs(+OptPascal, NextOptPascal) is a helper function for optpascal/2.
% Given one OptPascal list, it generates the next by adding adjacent
% items, but if the last two items are unequal, then their sum is
% repeated. This is intended to be a deterministic predicate, and to
% avoid a probable compiler limitation, we therefore use one cut.
add_pairs([], []).
add_pairs([X], [X]).
add_pairs([X,Y], Ans) :-
S is X + Y,
(X = Y -> Ans=[S] ; Ans=[S,S]),
!. % To overcome potential limitation of compiler
add_pairs( [X1, X2, X3|Xs], [S|Ys]) :-
S is X1 + X2,
add_pairs( [X2, X3|Xs], Ys).
</lang>
===Solutions===
Solutions with output from SWI-Prolog:
<lang prolog>
%%% Task 1: "A method to generate the coefficients of (1-X)^p"
coefficients(N, Coefficients) :-
pascal(N, X),
alternate_signs(X, Coefficients).
alternate_signs( [], [] ).
alternate_signs( [A], [A] ).
alternate_signs( [A,B | X], [A, MB | Y] ) :-
MB is -B,
alternate_signs(X,Y).
%%% Task 2. "Show here the polynomial expansions of (x − 1)p for p in the range 0 to at least 7, inclusive."
coefficients(Coefficients) :-
optpascal( Opt),
pascalize( Opt, Row ),
alternate_signs(Row, Coefficients).
% As required by the problem statement, but necessarily very inefficient:
:- between(0, 7, N), coefficients(N, Coefficients), writeln(Coefficients), fail ; true.
</lang>
<pre>
[1]
[1,-1]
[1,-2,1]
[1,-3,3,-1]
[1,-4,6,-4,1]
[1,-5,10,-10,5,-1]
[1,-6,15,-20,15,-6,1]
[1,-7,21,-35,35,-21,7,-1]
</pre>
The following would be more efficient because backtracking saves recomputation:
<pre>
:- coefficients(Coefficients),
writeln(Coefficients),
Coefficients = [_,N|_], N = -7.
</pre>
<lang prolog>
%%% Task 3. Use the previous function in creating [sic]
%%% another function that when given p returns whether p is prime
%%% using the AKS test.
% Even for testing whether a given number, N, is prime,
% this approach is inefficient, but here is a Prolog implementation:
prime_test_per_requirements(N) :-
coefficients(N, [1|Coefficients]),
append(Cs, [_], Coefficients),
forall( member(C, Cs), 0 is C mod N).
</lang>
The following is more efficient (because it relies on optpascal
lists rather than the full array of coefficients), and more
flexible (because it can be used to generate primes without requiring
recomputation):
<lang prolog>
prime(N) :- optpascal([1,N|Xs]), forall( member(X,Xs), 0 is X mod N).
</lang>
<lang prolog>
%%% Task 4. Use your AKS test to generate a list of all primes under 35.
:- prime(N), (N < 35 -> write(N), write(' '), fail ; nl).
% Output: 1 2 3 5 7 11 13 17 19 23 29 31
%%% Task 5. As a stretch goal, generate all primes under 50.
:- prime(N), (N < 50 -> write(N), write(' '), fail ; nl).
% Output: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
</lang>
=={{header|Python}}==
| |||