Testing Robinson numbers for primality

The reader is assumed to be familiar with searches for Proth primes and related forms using software such as Proth.exe, Newpgen.exe, Primeform.exe, Prp.exe, Winbitwin.exe, Titanix,exe, etc.

There are a number of ways of testing a positive integer p for primality. These include :

1. a full sieve to the root of p;
2. variations of the p- 1 methods developed by Brillhart, Morrison and Selfridge, based on earlier results by Lucas, Proth and Pocklington, wherein p- 1 is factored completely or partially and the factors used to test for pseudoprimality.
3. variations of the p+1 methods developed by Brillhart, Morrison and Selfridge from earlier ideas by Lucas and Lehmer.
4. combinations of both of the previous methods.
5. generic primality testing algorithms such as ECPP (Elliptic Curve Primality Proving), by Atkin and Morain (Titanix.exe is an implementation of this), and APR-CL (Adleman, Pomerance, Rumely, Cohen , Lenstra).

In practice, whether for finding Proth primes, primes in arithmetic progression, Cunningham chains, etc., interest will usually be in searching across large ranges of numbers of the form k*2n +1, where the p- 1 Proth test can be used. The initial search space (i.e. the entire set of numbers to be considered) is substantially restricted by using a partial sieve to a manageable limit, as it done by both Proth.exe and Newpgen.exe. These programs can be used to build lists of combinations k & n which may then be tested for pseudoprimality using Prp.exe and then primality using Proth.exe or Primeform.exe. Note that the generic algorithms are not equipped to cope with numbers of the sizes typically considered here.

I am interested in the typical number of pseudoprimality / primality tests that have to be carried out across a close range (I mean by this that values of n are approximately equal) in order to locate a prime. In particular, in searching for Keller primes, I am interested in testing a fixed and limited number of k values over given n ranges. Since Newpgen.exe is not suited to this, the alternative is to generate quickly an initial test set using a very brief sieve and then passing the output of this to Proth.exe, using the "Factors only" preference and with a fixed manual sieve limit. The idea of a fixed limit sieve is important in what follows.

Now for some theory : It is widely known (and I won't give references) that p (x), the number of primes less than or equal to x, is approximately equal to and that the likelihood that x is prime is approximately . But what if x (or p, since we are interested in primes) has already survived a sieve to a limit q ? Now, it is obvious that the proportion of integers surviving a sieve to q is s(q) = . If p has survived a sieve to q, then the likelihood that p is a prime is therefore , or where t(q) = , and the expected number of tests required in order to obtain a prime is the inverse of this. A classical result by Mertens implies that t(q) ® eg .log(q) as q ® ¥ , where g is Euler's constant, and so the value of t(q) rises logarithmically. The two tables below comparative values between the calculated value and the estimated value for a variety of key limits.

 q t(q) (calculated) t(q) (estimated) 10 4.375 4.101 102 8.31135737892 8.202 103 12.3509756739 12.3032 104 16.4244896322 16.4043 105 20.5115928252 20.50535 106 24.6073829476 24.6064 107 28.7077703609 28.7075 108 32.808698609 32.8086

and

 q t(q) (calculated) t(q) (estimated) 2 2 1.2345 22 3 2.469 23 4.375 3.7036 24 5.21354166667 4.938 25 6.54226970908 6.173 26 7.59951458813 7.4073 27 8.78222652931 8.642 28 9.96479475259 9.876 29 11.2037429513 11.1109 210 12.3997465887 12.34545 211 13.6141194455 13.58 212 14.8463264797 14.81454 213 16.0642635225 16.049 214 17.2996827618 17.2836 215 18.5252325284 18.5182 216 19.7576704153 19.7527 217 20.9920980308 20.98727 218 22.2243300099 22.1816 219 23.4592887593 23.45636 220 24.692296376 24.6909 221 25.9266589754 25.92545 222 27.1608713184 27.16 223 28.3950646914 28.39454 224 29.6294155136 29.62909 225 30.864034405 30.8636 226 32.098384759 32.09818 227 33.33284689 33.33272

Consider p = k*2n + 1. Then log (p) » n*log(2) + log (k), and if k is small in comparison to n, then we can take log (p) » n*log(2). Then the expected number of tests required on numbers surviving a sieve to q (rounding up to nearest integer) is :

 q \ n 10000 20000 50000 100000 200000 105 338 676 1690 3380 6759 106 282 564 1409 2817 5634 107 242 483 1208 2415 4829 108 212 423 1057 2113 4226