login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089105 Values taken by least witness function W(n). 3
2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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

REFERENCES

Balasubramanian, R., and S. V. Nagaraj. "The least witness of a composite number." In Information Security, LNCS 1396 (1998), pp. 66-74.

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

LINKS

Table of n, a(n) for n=1..20.

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.

CROSSREFS

Cf. A089825, A007916.

Sequence in context: A129125 A259444 A071591 * A028769 A094784 A085971

Adjacent sequences:  A089102 A089103 A089104 * A089106 A089107 A089108

KEYWORD

nonn,hard

AUTHOR

N. J. A. Sloane, Jan 18 2004

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 30 04:01 EST 2020. Contains 338781 sequences. (Running on oeis4.)