Millions of Perrin pseudoprimes including a few giants

Abstract

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.