World!Of
Numbers  WON plate
125 |

[ 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 * 31241 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 * 1914678481191735161 is prime 17 10^16 + 6286491369 Jan 10, 2007 FaridehFiroozbakht squarefreeComment 18 10^17 + 10102756401 Jan 13, 2007 FaridehFiroozbakht squarefree 19 10^18 + 114865704261 May 2, 2005 Jens KruseAndersen squarefreeComment 20 10^19 + 494514450733 May 2, 2005 Jens KruseAndersen 3027650429 * 3302891377494514450733 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 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 ?   Pinch, R. G. E., The Pseudoprimes up to 10^13.

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 Prime Curios! Prime Puzzle  Wikipedia 125 Le nombre 125 ```

```

[ TOP OF PAGE]

Patrick De Geest - Belgium - Short Bio - Some Pictures