Appendix 5. Prime table
(Primes near to 2^n, 10^n, factorial, primorial and compositorial)
(January 18, 2009)
[Japanese]
Abstract
In case we generate a ndigit prime number, the most primitive method is,
First, generate a random odd number and check the primarity,
If failed, add 2 and check the primarity,
repeat this procedure until the prime is found.
Almost all number choosed at random is usually composite,
so not starting from definite primarity check,
first we should check it is divisible by small primes (3, 5, 7), then filter by Fermat test.
In many cases, chosen number is sieved out, then we should try more definite primarity test.
We try to search,
by this primitive method.
The number of primes are,
 Smaller and larger 10 primes for small n
 Smallest and largest primes for large n
(Because the computation time for searching 10 primes is ten times of that of one prime,
and the time for primarity check becomes longer.)
 Small differences (i.e. N ± 1, 3, 5, 7, 9).
Primarity is checked by SoloveyStrassen test for base = 2, 3, 5, 7, 11, 13, 17, 19.
(So accurately say, they are probable prime.
But in very lowest possibility, then are all primes.)
We should finally check strict primarity by APRTCLE or ECPP.
Prime table
[1] nbit prime
First and last 10 nbit primes (bit length n=2, ... , 2600 : Jan. 18, 2009)
First and last nbit primes (bit length n=2, ... , 4320 : Dec. 21, 2008)
Primes of form 2^{n}±1, 3, 5, 7 and 9 (n=1, ... , 4320 : Dec. 01, 2008)


nbit prime number N lies between 2^{n1} ≤ N ≤ 2^{n}1.
We search for the primes within these ranges from higher (2^{n}1)
and lower (2^{n1}) numbers.
This table means the primes near 2^{n}.
These primes are available for generating the key pair of RSA.

The end of search range is up to n=4321 (computation limit of modpow in UBASIC (1300 digits)).
 Legend

[2] Primes near 10^{n}
First and last 10 primes near to 10^{n}
(n=1, ... , 500 : Dec. 01, 2008)
First and last primes near to 10^{n}
(n=1, ... , 1300 : Dec. 11, 2008)
Primes near to 10^{n} in small difference
(form 10^{n}±3, 9, 10^{n}+1, 7)
(n=1, ... , 1300 : Dec. 01, 2008)


We search for the primes near to 10^{n}.
This table is also the smallest and largest primes in each digits.
And these results are related to prime gap near 10^{n}.

The end of search range is up to n=1300 (computation limit of modpow in UBASIC).
 Legend

[3] Primes near to factorial, primorial and compositorial


(n1)!+1 is divisible by n iff n is prime (Wilson's Theorem).
And N=n!±k (k=2, ... , n) has trivial factors.
In the other cases, primarity and trivial factors are unknown.
I searched for the primes near to n! (factorial of n)
up tp n=561 (computation limit of modpow in UBASIC).

#P_{n} denotes the pruduct of primes up to nth prime.
#P_{n} = P_{1} * P_{2} * ... * P_{n}
This product is often called as "primorial" from the analogy of "factorial".
This number is used for the proof of the infinity of the number of primes,
because #P_{n}+1 is not divisible by P_{k} (k=1, ... ,n).
I searched for the primes near to #P_{n}
up to n=437 (Pn=3049) (computation limit of modpow in UBASIC).

From the analogy of factorial and primorial, we name the product of composite numbers
as "Compositorial".
(Caution ! : This term is not commonly used. We use it only in this page.)
For example, in case of n=10, factorial, primorial, compositorial are as follows;
F : 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
P : 2 * 3 * 5 * 7
C : 4 * 6 * 8 * 9 * 10
Compositorial #Comp_{n} is represented as
#Comp_{n} = n! / #P_{k}
where k is the largest number such that P_{k} ≤ n.
We search for the primes near to #Comp_{n}
up to n=538 (Cn=658) (computation limit of modpow in UBASIC).

Legend
[1] nbit primes
For n less than 7, all primes are in a list (because the number of primes is smaller than 10).
For example,
5  1, 3, 7, 13, 15
denotes
2^{4}+1 (=17)
2^{4}+3 (=19)
2^{4}+7 (=23)
2^{4}+13 (=29)
2^{4}+15 (=31)
are the 5 bit primes.
For n larger than 7, first and last 10 primes are in a list.
For example,
8  3, 9, 11, 21, 23, 29, 35, 39, 45, 51  59,57,45,33,29,27,23,17,15,5
denotes
2^{7}+3 (=131)
2^{7}+9 (=137)
...
2^{7}+45 (=173)
2^{7}+51 (=179)
...
...
2^{8}59 (=197)
2^{8}57 (=199)
...
2^{8}15 (=241)
2^{8}5 (=251)
are the first and last 10 8bit primes.
[2] Primes near to 10^{n}
last 10 primes nearest to 10^n (form 10^na) [n] first 10 primes nearest to 10^n (form 10^n+a)
[]
8, 7, 5, 3 [1] 1, 3, 7, 9, 13, 19, 21, 27, 31, 33
denotes
10^{1}8 (=2)
10^{1}7 (=3)
10^{1}5 (=5)
10^{1}3 (=7)
are the primes smaller than 10^{1}, and
10^{1}+1 (=11)
10^{1}+3 (=13)
...
10^{1}+31 (=41)
10^{1}+33 (=43)
are the primes larger than 10^{1}
Furthur computation
 Extend the search range for first and last primes
 Strict primarity check with APRTCLE or ECPP
Email : kc2hmsm@asahinet.or.jpHisanori Mishima