WON TOPIC 125

World!Of
Numbers

WON plate
125 |

[ February 11, 2002 ]
The smallest composites of length n that are
pseudoprime to base 2.

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.

Length 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 + ? - - -

20 10^19 + ? - - -

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 :

I found the smallest number m, where prime(m)*(2prime(m)-1) > 10^16.
This number is 4157408.
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) ⁽¹⁾

Hence from ⁽¹⁾ we conclude that,

n is a 2-base pseudoprime iff 2^(n-1) = 1 (mod 2p-1) ⁽²⁾

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) ⁽³⁾
and from ⁽²⁾ & ⁽³⁾ we deduce that,

n is a 2-base pseudoprime iff 2^(p-1) = 1 (mod 2p-1) ⁽⁴⁾

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 ⁽⁴⁾ 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.