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

Author

N. J. A. Sloane, Jan 18 2004

Keywords

• nonn
• hard

Comments

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

References

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

Links

• 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.

Crossrefs

Cf. A089825, A007916.

Extensions

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