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



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089105 Values taken by least witness function W(n). 3


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

%N Values taken by least witness function W(n).

%C 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

%C Comment from _Don Reble_, May 27 2014 (Start):

%C It has because of

%C ------ ----------------------------

%C 18 565491872244422701441

%C 20 76786041519852770748961

%C 21 1747624437573692208710761

%C 24 79962397898771029747829041

%C Alas, those are merely upper-bounds on the A089825 values.

%C (End)

%C 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

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

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

%H W. R. Alford, A. Granville, and C. Pomerance (1994). "<a href="http://www.math.dartmouth.edu/~carlp/PDF/reliable.pdf">On the difficulty of finding reliable witnesses</a>". Lecture Notes in Computer Science 877, 1994, pp. 1-16.

%Y Cf. A089825, A007916.

%K nonn,hard

%O 1,1

%A _N. J. A. Sloane_, Jan 18 2004

%E Missing values a(11) and a(14) added by _Charles R Greathouse IV_, Sep 07 2011, based on Sep 24 2010 SeqFan posting

%E a(13)-a(20) from _Charles R Greathouse IV_, May 27 2014 based on comments from _Charles R Greathouse IV_ and _Don Reble_

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 January 17 11:30 EST 2021. Contains 340240 sequences. (Running on oeis4.)