|
[ February 11, 2002 ]
The smallest composites of length n that are
pseudoprime to base 2
Extra info pseudoprime to base 2 (Poulet Number)
The smallest composite pseudoprime to base 2 is 341.
So we start the table with length 3.
Can you extend this list up to let's say... length 999 ?
If you should find the smallest titanic number of length 1000
then you should submit it to Shyam Sunder Gupta
as it will be the solution to his CYF NO. 1.
| Len | Composite | When | Who | Comment |
| 3 | 10^2 + 241 = 341 | 1819 | Sarrus | Semiprime = 11 * 31
241 is prime |
| 4 | 10^3 + 105 = 1105 | - | - | - |
| 5 | 10^4 + 261 = 10261 | - | - | Semiprime = 31 * 331 |
| 6 | 10^5 + 1101 = 101101 | - | - | - |
| 7 | 10^6 + 4653 | Feb 11, 2002 | pdg | - |
| 8 | 10^7 + 4681 | Feb 11, 2002 | pdg | - |
| 9 | 10^8 + 17223 | Feb 11, 2002 | pdg | - |
| 10 | 10^9 + 1152801 | Feb 11, 2002 | pdg | - |
| 11 | 10^10 + 321321 | Feb 11, 2002 | pdg | 4253 * 2351357 |
| 12 | 10^11 + 4790097 | Feb 11, 2002 | pdg | - |
| 13 | 10^12 + 1376901 | Feb 12, 2002 | pdg | 577351 * 1732051 |
| 14 | 10^13 + 130243671 | Feb 18, 2002 | Gupta | 2390473 * 4183327 |
| 15 | 10^14 + 105970311 | Feb 19, 2002 | Gupta | 581239 * 172046449 |
| 16 | 10^15 + 191735161 | Feb 21, 2002 | Gupta | 522281 * 1914678481
191735161 is prime |
| 17 | 10^16 + 6286491369 | Jan 10, 2007 | Farideh
Firoozbakht | squarefree
Comment |
| 18 | 10^17 + 10102756401 | Jan 13, 2007 | Farideh
Firoozbakht | squarefree |
| 19 | 10^18 + 114865704261 | May 2, 2005 | Jens Kruse
Andersen | squarefree
Comment |
| 20 | 10^19 + 494514450733 | May 2, 2005 | Jens Kruse
Andersen | 3027650429 * 3302891377
494514450733 is prime |
| 21 | 10^20 + ? | - | - | - |
| 22 | 10^21 + ? | - | - | - |
| 23 | 10^22 + ? | - | - | - |
| 24 | 10^23 + ? | - | - | - |
| 25 | 10^24 + ? | - | - | - |
| 26 | 10^25 + ? | - | - | - |
Distribution laws of the pseudoprimes
Carlos Rivera found something interesting about the question
What is the probability that a composite number of K digits
is pseudoprime to base 2 ?
On page 28 of R. K. Guy's well known book
(UPiNT, Vol.1, 2nd ed.) we may read that the quantity
of numbers pseudoprimes base 2 less than x, P2(x),
is bound by the following formulas due to C. Pomerance :
e^(ln x^(5/14)) < P2(x) < x.e^((-ln x.lnlnln x)/2lnln x)
(Pomerance) has a heuristic argument that the true estimate
is the upper bound with the 2 omitted
This estimative formula for the population of pseudoprimes
base 2 is what we need to estimate the probability
that a random number of K digits is psp(2).
According with the upper bound the probability that
a (any) random number is psp(2) is approximately P2(2)/x,
or e^((-ln x.lnlnln x)/lnln x) (following the indication of
Pomerance about eliminating the 2 for the upper bound).
Consequently the average quantity of numbers that need
to be tested before we get ONE SINGLE psp(2) is
1/e^((-ln x.lnlnln x)/lnln x) or e^((ln x.lnlnln x)/lnln x).
Well, when the number we are looking for in CYF1 is of
1000 digits we may equate x = 10^999. For this x
then e^((ln x.lnlnln x)/lnln x) approx. equals to 1.3*10^264.
Consequently this target (CYF1) is nowadays out of reach
IF the Pomerance formulas are right.
Even numbers much smaller that 1000 digits are practically
out of reach. E.g. 50 digits, as you can verify yourself
calculating e^((ln x.lnlnln x)/lnln x) for x = 10^49.
C. Caldwell's site is very informative regarding this topic.
See page Probable-primes: How Probable?
With this information the readers can themselves
calculate the degree of difficulty for the task ahead !
See A068216 for
Smallest n-digit pseudoprimes (in base 2).
See A067845 for Gupta's largest solutions
Largest n-digit pseudoprimes (in base 2).
Similar to the above list, Shyam Sunder Gupta created
sequences also for STRONG pseudoprimes to base 2.
Smallest n-digit strong pseudoprimes (in base 2).
Largest n-digit strong pseudoprimes (in base 2).
The last term has a length of 16. Are longer lengths known ?
More websites about pseudoprimes
Pinch, R. G. E., The Pseudoprimes up to 10^13.
Farideh Firoozbahkt comments her approach
Yes, I proved the following proposition:
If p & 2p-1 are odd prime then p*(2p-1) is base-2 psp iff p = 1 (mod 12)
So there exist many base-2 psp of the form p*(2p-1).
Also it seems that there exist infinitely many base-2 psp numbers
of the form p*(kp-k+1).
For finding a(17) (the first 17-digit base-2 psp) the steps were :
1. I found the smallest number m, where prime(m)*(2prime(m)-1) > 10^16.
This number is 4157408.
2. I found the smallest non-negative number m, where
prime(m+4157408)*(2prime(m+4157408)-1) is a base-2 psp.
This number is 1.
Hence the smallest base-2 psp of the form p*(2p-1) is
n = prime(4157408+1)*(2prime(4157408+1)-1) = 10000008663854653.
So a(17) = 10000008663854653.
Then I found a(17).
As I remember there exists only one base-2 psp number r between a(17) and n
(r = 10000008250001701 = 50000021*200000081 = 50000021*(4*50000021-3)).
Similarly for finding a(18) at first I found some upper bound for a(18)
of the form p*(kp-k+1)). Then I tried to find a(18).
With the approach I get a candidate that is not necessarily the smallest.
I used two computers, with one of them upwards searching from 10^16 and
with the other a downwards search from 10000008663854653.
Proof of the proposition:
If p & 2p-1 are odd prime then p*(2p-1) is base-2 psp iff p = 1 (mod 12)
Since p is prime by Fermat's little theorem (FLT) we have,
2^p = 2 (mod p) so 2^(p*(2p-1)) = 2^(2p-1) = (2^p)*(2^(p-1)) (mod p)
but 2^(p-1) = 1 (mod p) hence 2^n = 2 (mod p) and since p is odd
we deduce that,
2^(n-1) = 1 (mod p) (1)
Hence from (1) we conclude that,
n is a 2-base pseudoprime iff 2^(n-1) = 1 (mod 2p-1) (2)
But 2p-1 is prime hence by FLT we have 2^(2p-1) = 2 (mod 2p-1)
therefore 2^((2p-1)*p) = 2^p (mod 2p-1) hence
2^(n-1) = 2^(p-1) (mod 2p-1) (3)
and from (2) & (3) we deduce that,
n is a 2-base pseudoprime iff 2^(p-1) = 1 (mod 2p-1) (4)
Now if q = 2p-1 according to Euler's criterion (2/q) = 2^((q-1)/2) (mod q)
or (2/q) = 2^(p-1) (mod q) and by using (4) we conclude that,
n is a 2-base pseudoprime iff (2/q) = 1 (mod q)
A theorem says (one of the applications of Gauss's lemma)
(2/q) = 1 (mod q) iff q= 1 or -1 (mod 8),
but since p is odd q = 2p-1 cannot be of the form 8k-1 hence,
n is a 2-base pseudoprime iff q = 1 (mod 8),
namely,
n is a 2-base pseudoprime iff p = 1 (mod 4)
but since p & 2p-1 are primes, p cannot be of the form
12k+5 & 12k+9, so
n is a 2-base pseudoprime iff p = 1 (mod 12)
and the proof is complete.
Hope the explanations are clear.
Message from Jens Kruse Andersen send in a few times way back in
2005 but that unfortunately got lost, until now [ Nov 17, 2008 ] !
Smallest 2-psp with 17, 18, 19, 20 digits:
10^16+6286491369 = 17 * 19 * 29 * 127 * 25609 * 328249
10^17+10102756401 = 11 * 31 * 37 * 79 * 109 * 673 * 701 * 1951
10^18+114865704261 = 29 * 31 * 173 * 271 * 30493 * 778081
10^19+494514450733 = 3027650429 * 3302891377
(494514450733 is prime)
My program agrees with the listed results below 17 digits.
It uses 64-bit numbers so it cannot search at 10^20.
The page now lists Farideh Firoozbakht in 2007 for the first 2 numbers.
If the page is updated then it's OK to keep Farideh for those numbers.
The page says x.e^(-ln x.lnlnln x)/2lnln x) several times.
It is missing "(" and should be x.e^((-ln x.lnlnln x)/2lnln x)
I cannot explain the loss of this submission. Anyway my
sincere apologies for this, Jens Kruse Andersen. And thanks for
reporting the typo's in the formulae. They've been taken care of [pdg].
| 
A000125 
TOP OF PAGE]
- Short Bio - Some Pictures