Last updated 10pm GMT 05 March 2011.
I was inspired by Thomas R. Nicely's page about GMP mpz_spsp's, and it made me want to test it in the newest version
5.0.1 of GMP.
I downloaded "gmp-5.0.1.tar.gz" (2631904 bytes) from the main GMP site and compiled it on a freshly installed Msys
with MinGW64. The variables "__GNU_MP_VERSION", "__GNU_MP_VERSION_MINOR", "__GNU_MP_VERSION_PATCHLEVEL" reports
respectively 5, 0 and 1, but the variable "gmp_version" reports 4.3.2. I assume they forgot to update "gmp_version".
I counted all mpz_spspk's below 5*10^10 to compare with earlier GMP versions:
GMP 4.1.2 GMP 4.2.1/4.3.1 GMP 5.0.1
-------------------------------------
mpz_spsp1: 543 559 546
mpz_spsp2: 70 68 67
mpz_spsp3: 19 11 11
mpz_spsp4: 3 0 0
mpz_spsp5: 0 0 0
I have since continued counting mpz_spspk's in GMP 5.0.1:
10^10 5*10^10 10^11 10^12 4*10^12
------------------------------------
mpz_spsp1: 294 546 690 1833 3276
mpz_spsp2: 38 67 80 224 400
mpz_spsp3: 4 11 15 42 81
mpz_spsp4: 0 0 0 4 13
mpz_spsp5: 0 0 0 0 3
Here is a list of all 3773 mpz_spspk's up to 4*10^12: mpz_spsp.txt
Out of the 3773 numbers there is 3523 with 2 prime factors, 207 with 3 factors, 40 with 4 factors and 3 with 5 factors.
Out of the 3523 numbers with 2 factors, 3187 of them are of a special form p*(ap-(a-1)) for a>=2:
p*(2p-1) 1095 numbers
p*(3p-2) 856 numbers
p*(4p-3) 390 numbers
p*(5p-4) 156 numbers
p*(6p-5) 186 numbers
p*(7p-6) 131 numbers
p*(ap-(a-1)) for a>7 373 numbers
_______________________________________________________________________________________________________________________
I also tested numbers of the form p*(2p-1) with p and (2p-1) prime for p<10^8:
GMP 4.1.2 GMP 4.2.1/4.3.1 GMP 5.0.1
-------------------------------------
mpz_spsp0 377353 377554 377543
mpz_spsp1 35836 35772 35772
mpz_spsp2 7996 7911 7911
mpz_spsp3 1802 1782 1782
mpz_spsp4 413 401 401
mpz_spsp5 89 86 86
mpz_spsp6 31 21 21
mpz_spsp7 4 3 3
mpz_spsp8 1 2 2
mpz_spsp9 1 0 0
I continued this search for GMP 5.0.1 for p>10^8:
p<10^8 p<10^10 p<10^11 p<10^12 p<4*10^12
---------------------------------------------------
mpz_spsp0 377543 23694036 194504553 1625415918 5878749855
mpz_spsp1 35772 2237331 4060508 153484825 555158269
mpz_spsp2 7911 494514 920945 33946445 122764371
mpz_spsp3 1782 112009 213135 7695720 27840928
mpz_spsp4 401 26001 50621 1783895 6452866
mpz_spsp5 86 6219 12042 420782 1522576
mpz_spsp6 21 1447 2929 100722 365846
mpz_spsp7 3 323 702 24406 88290
mpz_spsp8 2 92 185 6025 21681
mpz_spsp9 0 16 51 1478 5337
mpz_spsp10 0 7 11 369 1322
mpz_spsp11 0 3 3 93 337
mpz_spsp12 0 0 0 18 71
mpz_spsp13 0 0 0 4 22
mpz_spsp14 0 0 0 1 7
mpz_spsp15 0 0 0 0 1
Here is a list of all mpz_spspk's with order>=10 of the form p*(2p-1) for p<4*10^12: mpz_spsp p(2p-1).txt
Notice in the table for p<4*10^12 there are 714,221,924 mpz_spsp order 1 to 15 out of a total of 714,221,924 +
5,878,749,855 = 6,592,971,779 total primes (2p-1). That means almost every 9th p*(2p-1) where p and 2p-1 are primes is
a mpz_spspk.
The reason for this is probably related conjecture 2 in this paper by Brian C. Higgins: higgins.pdf
which I found on oeis.org: http://oeis.org/A090659
The paper is about non-witnesses for Miller-Rabin strong probable primes which is the test mpz_probab_prime_p uses.
For numbers n=p*q with p=2r+1 and q=4r+1=2p-1 and r odd, the number of non-witnesses is equal to (p-1)*(q-1)/4 which is
almost the highest possible ratio 1/4, proved by Rabin, of the values 1 to p*q-1.
I tested the conjecture for p<5*10^8 and it checks out. When p and q are not 2r+1 and 4r+1 for odd r, the number of non-
witnesses is slightly smaller than (p-1)*(q-1)/4 but still high. I also checked numbers of the form p*(ap-(a-1)) for a>2
and they also have a high number of non-witnesses, though lower than for p*(2p-1).
_______________________________________________________________________________________________________________________
During my search I also looked for first occurences mpz_spspk's of increasing order:
mpz_spsp1: 1,537,381 = 877*1753
mpz_spsp2: 1,943,521 = 61*151*211
mpz_spsp3: 465,658,903 = 15259*30517
mpz_spsp4: 239,626,837,621 = 346141*692281
mpz_spsp5: 2,028,576,353,203 = 1007119*2014237
mpz_spsp8: 14,910,591,535,003 = 2730439*5460877
Notice how all but mpz_spsp2 are of the form p*(2p-1). It's also interesting why I didn't find any mpz_spsp6 and
mpz_spsp7 between mpz_spsp5 and mpz_spsp8, but I did search all composites in that entire range barring any mal-
function of my program.
I tested all of the mpz_spspk's on Thomas R. Nicely's page in GMP 5.0.1. Many of them, including many of those order
10-12, are now mpz_spsp0 (not mpz_spsp pseudoprimes at all) in 5.0.1, which means they must have changed bases for
Miller Rabin tests in mpz_probab_prime_p in GMP 5.0.1. I wrote their orders in previous GMP verions after the numbers.
I also saved several of the higher order mpz_spspk's as I found them up to mpz_spsp16. Here is the list: spsp.txt.