1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    2/*	Nan.Numerics.Prime
    3	A simple prime number library
    4	Copyright 2016 Julio P. Di Egidio
    5	<mailto:julio@diegidio.name>
    6	<http://julio.diegidio.name/Projects/Nan.Numerics.Prime/>
    7	
    8	This file is part of Nan.Numerics.Prime.
    9	
   10	Nan.Numerics.Prime is free software: you can redistribute it and/or modify
   11	it under the terms of the GNU General Public License as published by
   12	the Free Software Foundation, either version 3 of the License, or
   13	(at your option) any later version.
   14	
   15	Nan.Numerics.Prime is distributed in the hope that it will be useful,
   16	but WITHOUT ANY WARRANTY; without even the implied warranty of
   17	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   18	GNU General Public License for more details.
   19	
   20	You should have received a copy of the GNU General Public License
   21	along with Nan.Numerics.Prime.  If not, see <http://www.gnu.org/licenses/>.
   22*/

   23%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   24
   25% (SWI-Prolog 7.3.25)

   26
   27% TODO: Implement dynamic wheel with option for level?

   28
   29:- module(prime_whl, []).
   30
   31:- public
   32	test_/2,		% +N:posint, -Cert:boolean

   33	right_/3,		% +N:posint, -P:posint, -Cert:boolean

   34	left_/3,		% +N:posint, -P:posint, -Cert:boolean

   35	lev_/1.			% -Lev:posint

A simple prime number library :: wheel

Module prime_whl provides low-level predicates to test candidate primality of numbers based on a prime wheel of level 4, i.e. generated by the first 4 consecutive prime numbers.

NOTE: Predicates in this module are not meant for public use.

author
- Julio P. Di Egidio
version
- 1.2.5-beta
copyright
- 2016 Julio P. Di Egidio
license
- GNU GPLv3
To be done
- Implement dynamic wheel with option for level?
   52%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 test_(+N:posint, -Cert:boolean) is semidet
   55%

   56%	True if N is a candidate prime number.

   57%

   58%	Cert is =true= if N is certainly prime, otherwise it is =false=.

   59
   60test_(N, true) :-
   61	lr_a_(N, _, R), !, N == R.
   62test_(N, Cert) :-
   63	lro_p_(N, _, 0),
   64	cert_(N, Cert).
 right_(+N:posint, -P:posint, -Cert:boolean) is det
   67%

   68%	P is the smallest candidate prime number greater than or equal to N.

   69%

   70%	Cert is =true= if P is certainly prime, otherwise it is =false=.

   71
   72right_(N, P, true) :-
   73	lr_a_(N, _, P), !.
   74right_(N, P, Cert) :-
   75	lro_p_(N, _, ROff),
   76	P is N + ROff,
   77	cert_(P, Cert).
 left_(+N:posint, -P:posint, -Cert:boolean) is semidet
   80%

   81%	P is the greatest candidate prime number less than or equal to N.

   82%	Fails if N equals =1=.

   83%

   84%	Cert is =true= if P is certainly prime, otherwise it is =false=.

   85
   86left_(1, _, _) :- !, fail.
   87left_(N, P, true) :-
   88	lr_a_(N, P, _), !.
   89left_(N, P, Cert) :-
   90	lro_p_(N, LOff, _),
   91	P is N - LOff,
   92	cert_(P, Cert).
   93
   94%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 lev_(-Lev:posint) is det
   97%

   98%	Lev is the number of consecutive prime numbers starting from =2= that

   99%	generate this wheel.

  100
  101lev_(4/*lev*/).
  102
  103%	lr_a_(+N:posint, -L:posint, -R:posint) is semidet.

  104
  105lr_a_(N, L, R) :-
  106	N < 11/*la+1*/,
  107	whl_a_(N, L, R).
  108
  109%	lro_p_(+N:posint, -LOff:nonneg, -ROff:nonneg) is det.

  110
  111lro_p_(N, LOff, ROff) :-
  112	N0 is N - 11/*la+1*/,
  113	I0 is N0 mod 210/*lp*/,
  114	whl_p_(I0, LOff, ROff).
  115
  116%	cert_(+N:posint, -Cert:boolean) is det.

  117
  118cert_(N, true) :-
  119	N < 121/*(la+1)^2*/, !.
  120cert_(_, false).
  121
  122%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  123
  124whl_lev_(4).
  125
  126whl_la_(10).
  127
  128whl_lp_(210).
  129
  130whl_a_(1, 0, 2).
  131whl_a_(2, 2, 2).
  132whl_a_(3, 3, 3).
  133whl_a_(4, 3, 5).
  134whl_a_(5, 5, 5).
  135whl_a_(6, 5, 7).
  136whl_a_(7, 7, 7).
  137whl_a_(8, 7, 11).
  138whl_a_(9, 7, 11).
  139whl_a_(10, 7, 11).
  140
  141whl_p_(0, 0, 0).
  142whl_p_(1, 1, 1).
  143whl_p_(2, 0, 0).
  144whl_p_(3, 1, 3).
  145whl_p_(4, 2, 2).
  146whl_p_(5, 3, 1).
  147whl_p_(6, 0, 0).
  148whl_p_(7, 1, 1).
  149whl_p_(8, 0, 0).
  150whl_p_(9, 1, 3).
  151whl_p_(10, 2, 2).
  152whl_p_(11, 3, 1).
  153whl_p_(12, 0, 0).
  154whl_p_(13, 1, 5).
  155whl_p_(14, 2, 4).
  156whl_p_(15, 3, 3).
  157whl_p_(16, 4, 2).
  158whl_p_(17, 5, 1).
  159whl_p_(18, 0, 0).
  160whl_p_(19, 1, 1).
  161whl_p_(20, 0, 0).
  162whl_p_(21, 1, 5).
  163whl_p_(22, 2, 4).
  164whl_p_(23, 3, 3).
  165whl_p_(24, 4, 2).
  166whl_p_(25, 5, 1).
  167whl_p_(26, 0, 0).
  168whl_p_(27, 1, 3).
  169whl_p_(28, 2, 2).
  170whl_p_(29, 3, 1).
  171whl_p_(30, 0, 0).
  172whl_p_(31, 1, 1).
  173whl_p_(32, 0, 0).
  174whl_p_(33, 1, 3).
  175whl_p_(34, 2, 2).
  176whl_p_(35, 3, 1).
  177whl_p_(36, 0, 0).
  178whl_p_(37, 1, 5).
  179whl_p_(38, 2, 4).
  180whl_p_(39, 3, 3).
  181whl_p_(40, 4, 2).
  182whl_p_(41, 5, 1).
  183whl_p_(42, 0, 0).
  184whl_p_(43, 1, 5).
  185whl_p_(44, 2, 4).
  186whl_p_(45, 3, 3).
  187whl_p_(46, 4, 2).
  188whl_p_(47, 5, 1).
  189whl_p_(48, 0, 0).
  190whl_p_(49, 1, 1).
  191whl_p_(50, 0, 0).
  192whl_p_(51, 1, 5).
  193whl_p_(52, 2, 4).
  194whl_p_(53, 3, 3).
  195whl_p_(54, 4, 2).
  196whl_p_(55, 5, 1).
  197whl_p_(56, 0, 0).
  198whl_p_(57, 1, 3).
  199whl_p_(58, 2, 2).
  200whl_p_(59, 3, 1).
  201whl_p_(60, 0, 0).
  202whl_p_(61, 1, 1).
  203whl_p_(62, 0, 0).
  204whl_p_(63, 1, 5).
  205whl_p_(64, 2, 4).
  206whl_p_(65, 3, 3).
  207whl_p_(66, 4, 2).
  208whl_p_(67, 5, 1).
  209whl_p_(68, 0, 0).
  210whl_p_(69, 1, 3).
  211whl_p_(70, 2, 2).
  212whl_p_(71, 3, 1).
  213whl_p_(72, 0, 0).
  214whl_p_(73, 1, 5).
  215whl_p_(74, 2, 4).
  216whl_p_(75, 3, 3).
  217whl_p_(76, 4, 2).
  218whl_p_(77, 5, 1).
  219whl_p_(78, 0, 0).
  220whl_p_(79, 1, 7).
  221whl_p_(80, 2, 6).
  222whl_p_(81, 3, 5).
  223whl_p_(82, 4, 4).
  224whl_p_(83, 5, 3).
  225whl_p_(84, 6, 2).
  226whl_p_(85, 7, 1).
  227whl_p_(86, 0, 0).
  228whl_p_(87, 1, 3).
  229whl_p_(88, 2, 2).
  230whl_p_(89, 3, 1).
  231whl_p_(90, 0, 0).
  232whl_p_(91, 1, 1).
  233whl_p_(92, 0, 0).
  234whl_p_(93, 1, 3).
  235whl_p_(94, 2, 2).
  236whl_p_(95, 3, 1).
  237whl_p_(96, 0, 0).
  238whl_p_(97, 1, 1).
  239whl_p_(98, 0, 0).
  240whl_p_(99, 1, 3).
  241whl_p_(100, 2, 2).
  242whl_p_(101, 3, 1).
  243whl_p_(102, 0, 0).
  244whl_p_(103, 1, 7).
  245whl_p_(104, 2, 6).
  246whl_p_(105, 3, 5).
  247whl_p_(106, 4, 4).
  248whl_p_(107, 5, 3).
  249whl_p_(108, 6, 2).
  250whl_p_(109, 7, 1).
  251whl_p_(110, 0, 0).
  252whl_p_(111, 1, 5).
  253whl_p_(112, 2, 4).
  254whl_p_(113, 3, 3).
  255whl_p_(114, 4, 2).
  256whl_p_(115, 5, 1).
  257whl_p_(116, 0, 0).
  258whl_p_(117, 1, 3).
  259whl_p_(118, 2, 2).
  260whl_p_(119, 3, 1).
  261whl_p_(120, 0, 0).
  262whl_p_(121, 1, 5).
  263whl_p_(122, 2, 4).
  264whl_p_(123, 3, 3).
  265whl_p_(124, 4, 2).
  266whl_p_(125, 5, 1).
  267whl_p_(126, 0, 0).
  268whl_p_(127, 1, 1).
  269whl_p_(128, 0, 0).
  270whl_p_(129, 1, 3).
  271whl_p_(130, 2, 2).
  272whl_p_(131, 3, 1).
  273whl_p_(132, 0, 0).
  274whl_p_(133, 1, 5).
  275whl_p_(134, 2, 4).
  276whl_p_(135, 3, 3).
  277whl_p_(136, 4, 2).
  278whl_p_(137, 5, 1).
  279whl_p_(138, 0, 0).
  280whl_p_(139, 1, 1).
  281whl_p_(140, 0, 0).
  282whl_p_(141, 1, 5).
  283whl_p_(142, 2, 4).
  284whl_p_(143, 3, 3).
  285whl_p_(144, 4, 2).
  286whl_p_(145, 5, 1).
  287whl_p_(146, 0, 0).
  288whl_p_(147, 1, 5).
  289whl_p_(148, 2, 4).
  290whl_p_(149, 3, 3).
  291whl_p_(150, 4, 2).
  292whl_p_(151, 5, 1).
  293whl_p_(152, 0, 0).
  294whl_p_(153, 1, 3).
  295whl_p_(154, 2, 2).
  296whl_p_(155, 3, 1).
  297whl_p_(156, 0, 0).
  298whl_p_(157, 1, 1).
  299whl_p_(158, 0, 0).
  300whl_p_(159, 1, 3).
  301whl_p_(160, 2, 2).
  302whl_p_(161, 3, 1).
  303whl_p_(162, 0, 0).
  304whl_p_(163, 1, 5).
  305whl_p_(164, 2, 4).
  306whl_p_(165, 3, 3).
  307whl_p_(166, 4, 2).
  308whl_p_(167, 5, 1).
  309whl_p_(168, 0, 0).
  310whl_p_(169, 1, 1).
  311whl_p_(170, 0, 0).
  312whl_p_(171, 1, 5).
  313whl_p_(172, 2, 4).
  314whl_p_(173, 3, 3).
  315whl_p_(174, 4, 2).
  316whl_p_(175, 5, 1).
  317whl_p_(176, 0, 0).
  318whl_p_(177, 1, 3).
  319whl_p_(178, 2, 2).
  320whl_p_(179, 3, 1).
  321whl_p_(180, 0, 0).
  322whl_p_(181, 1, 1).
  323whl_p_(182, 0, 0).
  324whl_p_(183, 1, 3).
  325whl_p_(184, 2, 2).
  326whl_p_(185, 3, 1).
  327whl_p_(186, 0, 0).
  328whl_p_(187, 1, 1).
  329whl_p_(188, 0, 0).
  330whl_p_(189, 1, 9).
  331whl_p_(190, 2, 8).
  332whl_p_(191, 3, 7).
  333whl_p_(192, 4, 6).
  334whl_p_(193, 5, 5).
  335whl_p_(194, 6, 4).
  336whl_p_(195, 7, 3).
  337whl_p_(196, 8, 2).
  338whl_p_(197, 9, 1).
  339whl_p_(198, 0, 0).
  340whl_p_(199, 1, 1).
  341whl_p_(200, 0, 0).
  342whl_p_(201, 1, 9).
  343whl_p_(202, 2, 8).
  344whl_p_(203, 3, 7).
  345whl_p_(204, 4, 6).
  346whl_p_(205, 5, 5).
  347whl_p_(206, 6, 4).
  348whl_p_(207, 7, 3).
  349whl_p_(208, 8, 2).
  350whl_p_(209, 9, 1).
  351
  352%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%