Lots and Lots of Perrin-Type Primality Tests and Their Pseudo-Primes

By Robert Dougherty-Bliss and Doron Zeilberger

.pdf    .tex

First Written: July 15, 2023; Previous version (with five additional DB-Z pseudoprimes): Aug. 2, 2023.

Appeared in INTEGERS, v. 23 (2023), #A95.

This version: Oct. 13, 2023 (adding the DB-Kauers even better powerful primality test)

We use Experimental Mathematics and Symbolic Computation (with Maple), to search for lots and lots of Perrin- and Lucas- style primality tests, and try to sort the wheat from the chaff. More impressively, we find quite a few such primality tests for which we can explicitly construct infinite families of pseudo-primes, rather, like in the cases of Perrin pseudo-primes and the famous Carmichael primes, proving the mere existence of infinitely many of them.

# C programs

See Robert D-B's github site

# Maple packages

• Perrin.txt, a Maple package to generate lots of Perrin-style Primality tests

• PerrinVV.txt, a Maple package to generate lots of Perrin-style Primality tests inspired by Vince Vatter's beautiful combinatorial proof of the Perrin property, and the Edlin-Zeilberger extension of the Goulden-Jackson cluster method. It is really depricated, since in hindsight it is simpler to use the general C-finite ansatz. It is mainly here for old time's sake.

# Sample Input and Output for Perrin.txt

• If you want to see all the Perrin-like primality tests where there is only one pseudo-prime less than 1000, and generated by compositions of at most 5 into at most 5 part, and all the pseudo=primes less than a million
the input file yields the output file

• If you want to see All the compositions C of N into k parts , for N from 1 to 7 and k from 1 to 7 f:=GenPerrin(C,x) has NO pseudo-primes <=10000 for, 2<=k<=7, 1<=N<=7, along with the pseudo-primes <=1600000
the input file yields the output file

• If you want to see All the compositions C of N into k parts , for N from 1 to 7 and k from 1 to 7 f:=GenPerrin(C,x) has <=1 pseudo-primes <=1000 for, 2<=k<=7, 1<=N<=7, along with the pseudo-primes <=100000
the input file yields the output file

# Sample Input and Output for PerrinVV.txt

• If you want to see the see all the Perrin Pseudo-primes less than a million (two of them)
the input file yields the output file

• If you want to see the see all the Pseudo-primes less than 400000 for the primality test inspired by circular words in {1,2,3}, avoiding (as consecutive subwords, aka factors) the words {11,222,3333}
the input file yields the output file

• If you want to see the see all the Pseudo-primes less than 100000 for the primality test inspired by circular words in {1,2,3,4}, avoiding (as consecutive subwords, aka factors) the words {11,222,3333,4444}
the input file yields the output file

• If you want to see the see all the Pseudo-primes less than 100000 for the primality test inspired by circular words in {1,2,3,4,5}, avoiding (as consecutive subwords, aka factors) the words {11,222,3333,4444,55555}
the input file yields the output file

• If you want to see the see all the Lucas-type Primality tests, along with their associated pseudo-primes up to 100000, for alphabets of size from 2 to 5 and ONE forbidden pattern (a constant word, i.e. the same letter repeated) of length from 2 to 7, along with the "champion" that happens to be Alphabet={1,2}, Patterns={[1,1,1]} (generating function (3-2*s-s^2)/(1-s-s^2-s^3), pseudo-primes: 182, 25201, 54289, 63618)
the input file yields the output file

• If you want to see the see all the Perrin-type Primality tests, along with their associated pseudo-primes up to 100000, for alphabets of size from 2 to 5 and TWO forbidden patterns (all constant word, i.e. the same letter repeated) of length from 2 to 7, along with the "champion" that happens to be the good old Perrin test (alphabet {1,2}, patterns {11,222})
the input file yields the output file

• If you want to see the see all the Perrin-type Primality tests, along with their associated pseudo-primes up to 100000, for alphabets of size from 2 to 5 and THREE forbidden patterns (all constant word, i.e. the same letter repeated) of length from 2 to 7, along with the "champion" that happens to be the natural analog of the Perrin test for an alphabet with 3 letters (alphabet {1,2,3}, patterns {11,222,3333})
the input file yields the output file

Articles of Doron Zeilberger