WIAS Preprint No. 2657, (2019)

Millions of Perrin pseudoprimes including a few giants


  • Stephan, Holger
    ORCID: 0000-0002-6024-5355

2010 Mathematics Subject Classification

  • 11B37 11B39 11B50


  • pseudoprimes, recurrence sequences, fast algorithm, large numbers




The calculation of many and large Perrin pseudoprimes is a challenge. This is mainly due to their rarity. Perrin pseudoprimes are one of the rarest known pseudoprimes. In order to calculate many such large numbers, one needs not only a fast algorithm but also an idea how most of them are structured to minimize the amount of numbers one have to test. We present a quick algorithm for testing Perrin pseudoprimes and develop some ideas on how Perrin pseudoprimes might be structured. This leads to some conjectures that still need to be proved.
We think that we have found well over 90% of all 20-digit Perrin pseudoprimes. Overall, we have been able to calculate over 9 million Perrin pseudoprimes with our method, including some very large ones. The largest number found has 1436 digits. This seems to be a breakthrough, compared to the previously known just over 100,000 Perrin pseudoprimes, of which the largest have 20 digits.
In addition, we propose two sequences that do not provide any pseudoprimes up to 1,000,000,000 at all.

Download Documents