help/prevcand

   1 NAME
   2     prevcand - previous candidate for primeness
   3
   4 SYNOPSIS
   5     prevcand(n [,count [, skip [, residue [, modulus]]]])
   6
   7 TYPES
   8     n           integer
   9     count       integer with absolute value less than 2^24, defaults to 1
  10     skip        integer, defaults to 1
  11     residue     integer, defaults to 0
  12     modulus     integer, defaults to 1
  13
  14     return      integer
  15
  16 DESCRIPTION
  17     The sign of n is ignored; in the following it is assumed that n >= 0.
  18
  19     prevcand(n, count, skip, residue, modulus) returns the greatest
  20     positive integer i less than abs(n) expressible as
  21     residue + k * modulus, where k is an integer, for which
  22     ptest(i,count,skip) == 1, or if there is no such integer i, zero.
  23
  24     If n < 2^32, count >= 0, and the returned value i is not zero, i is
  25     definitely prime.  If n > 2^32, count != 0, and i is not zero,
  26     i is probably prime, particularly if abs(count) is greater than 1.
  27
  28     With the default argument values, if n > 2, prevcand(n) returns the a
  29     probably prime integer i less than n such that every integer
  30     between i and n is composite.
  31
  32     If skip == 0, the bases used in the probabilistic test are random
  33     and then the probability that the returned value is composite is
  34     less than 1/4^abs(count).
  35
  36     If skip == 1 (the default value) the bases used in the probabilistic
  37     test are the first abs(count) primes 2, 3, 5, ...
  38
  39     For other values of skip, the bases used are the abs(count) consecutive
  40     integer skip, skip + 1, ...
  41
  42     If modulus = 0, the only values that may be returned are zero and the
  43     value of residue.  The latter is returned if it is positive, less
  44     than n, and is such that ptest(residue, count, skip) = 1.
  45
  46 RUNTIME
  47     The runtime for v = prevcand(n, ...) will depend strongly on the
  48     number and nature of the integers between n and v.  If this number
  49     is reasonably large the size of count is largely irrelevant as the
  50     compositeness of the numbers between n and v will usually be
  51     determined by the test for small prime factors or one pseudoprime
  52     test with some base b.  If N > 1, count should be positive so that
  53     candidates divisible by small primes will be passed over quickly.
  54
  55     On the average for random n with large word-count N, the runtime
  56     seems to be between roughly K/N^3 some constant K.
  57
  58 EXAMPLE
  59     > print prevcand(50), prevcand(2), prevcand(125,-1), prevcand(125,-2)
  60     47 1 113 113
  61
  62     > print prevcand(100,1,1,1,6), prevcand(100,1,1,-1,6)
  63     97 89
  64
  65     > print prevcand(100,1,1,2,6), prevcand(100,1,1,4,6),
  66     2 0
  67
  68     > print prevcand(100,1,1,53,0), prevcand(100,1,1,53,106)
  69     53 53
  70
  71     > print prevcand(125,1,3), prevcand(125,-1,3), prevcand(125,-2,3)
  72     113 121 113
  73
  74     > print prevcand(2e60, 1, 1, 31, 1e30)
  75     1999999999999999999999999999914000000000000000000000000000031
  76
  77 LIMITS
  78     none
  79
  80 LINK LIBRARY
  81     int zprevcand(ZVALUE n, long count, long skip, ZVALUE res, ZVALUE mod,
  82         ZVALUE *cand)
  83
  84 SEE ALSO
  85     nextcand, ptest
  86