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.