Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let W(n) be a function from the positive odd composite numbers to the least positive b such that n is not a b-strong pseudoprime. W(n) exists for all numbers in its domain and its range is unbounded. But I do not know which values it attains.

Clearly it cannot take on only values that are (nontrivial) powers. But can it take on all other values?

Crandall & Pomerance [1] list the known values of the range as 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 17, 19, and 23. Feitsma's calculations [2] allowed me to find the least n such that W(n) is 15, 22, and 37, respectively. I used Arnault's method [3] to find values giving 26, 29, 31, 34, 38, 41, 43, 46, 47.

I expect that all values other than proper powers are in the range. (There is good evidence that even 'difficult' values like 18 appear infinitely often.) But is anything known on this matter? Failing that, are there better methods for finding other small values in the range? Admission: I meant to read through Zhang & Tang [4] which may have better methods but have not yet done this.


[1] Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective (2nd edition), 2005.

[2] Jan Feitsma and William Galway, "Tables of pseudoprimes and related data: Computed by Jan Feitsma, arranged and edited by William Galway" (2010).

[3] F. Arnault, "Rabin-Miller primality test: composite numbers which pass it", Mathematics of Computation 64:209 (1995), pp. 355-361.

[4] Z. Zhang and M. Tang, "Finding Strong Pseudoprimes to Several Bases, II." Mathematics of Computation 72 (2003), pp. 2085-2097.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.