[ *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: