login
Values taken by least witness function W(n).
4

%I #26 Jul 07 2023 09:33:45

%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

%C Is this related to A341646? - _R. J. Mathar_, Jul 07 2023

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

%H Balasubramanian, R., and S. V. Nagaraj. <a href="https://doi.org/10.1007/BFb0030409">The least witness of a composite number</a>, In Information Security, LNCS 1396 (1998), pp. 66-74.

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