Pseudoprime Statistics to 10¹⁹

Abstract

A base-b pseudoprime (psp) is a composite N satisfying b ^N-1 = 1 (mod N). We use computer searches to count odd base-3 psp near 10ⁿ for n up to 19. The counts indicate that a good approximation to the probability of a random odd number near z being a psp is P(z) = z ^-0.59. Integrating P yields a pspcounting function, Q(x) = (x ^0.41)/0.82, which gives estimated counts close to known actual counts up to 10¹⁹, although these estimates are probably not valid for all x.

A table comparing pseudoprime counts up to 10¹¹ for bases 2, 3, 5, 7, 11, 13, 17, is included.

Keywords:

• Primary 11A99
• Psp
• pseudoprime