A089825 -id:A089825 - cp's OEIS frontend

A089105 Values taken by least witness function W(n).

2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26

Offset: 1

N. J. A. Sloane, Jan 18 2004

19, 22, 23, 26, 29, 31, 34, 37, 38, 41, 43, 46, and 47 are in this sequence.  Is this a duplicate of A007916? - Charles R Greathouse IV, Sep 07 2011
Comment from Don Reble, May 27 2014 (Start):
It has      because of
------  ----------------------------
   18      565491872244422701441
   20      76786041519852770748961
   21      1747624437573692208710761
   24      79962397898771029747829041
   Alas, those are merely upper-bounds on the A089825 values.
(End)
The least witness function W(k) is defined for odd composite numbers k. The sequence W(k) does not have its own entry in the OEIS because W(k) = 2 for all k with 9 <= k < 2047; then W(2047)=3. - N. J. A. Sloane, Sep 16 2014
Is this related to A341646? - R. J. Mathar, Jul 07 2023

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157 (pp. 168f in the 2nd edition).

W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
Balasubramanian, R., and S. V. Nagaraj. The least witness of a composite number, In Information Security, LNCS 1396 (1998), pp. 66-74.

Cf. A089825, A007916.

Missing values a(11) and a(14) added by Charles R Greathouse IV, Sep 07 2011, based on Sep 24 2010 SeqFan posting

a(13)-a(20) from Charles R Greathouse IV, May 27 2014 based on comments from Charles R Greathouse IV and Don Reble

A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.

Original entry on oeis.org

9, 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981

Offset: 1

N. J. A. Sloane

The tests are performed on sequential prime numbers starting with 2. Note that some terms are repeated.

Same as A014233 except for the first term.

			2047=23*89. 1373653 = 829*1657. 25326001 = 11251*2251. 3215031751 = 151*751*28351. 2152302898747 = 6763*10627*29947.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Matters Computational (The Fxtbook)
Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355-380.
G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp., 61 (1993), 915-926.
Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
S. Wagon, Primality testing, Math. Intellig., 8 (No. 3, 1986), 58-61.
Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Mathematics of Computation 72 (2003), pp. 2085-2097.
Index entries for sequences related to pseudoprimes

Cf. A089105, A089825.

Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). [Charles R Greathouse IV, May 17 2011]

Extended and description corrected by Jud McCranie Feb 15 1997.
a(10)-a(12) from Charles R Greathouse IV, Aug 14 2010
a(13)-a(14) copied from A014233 by Max Alekseyev, Feb 15 2017

cp's OEIS Frontend

A089105 Values taken by least witness function W(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions