Lots and Lots of PerrinType Primality Tests and Their PseudoPrimes
By Robert DoughertyBliss and Doron Zeilberger
.pdf
.tex
First Written: July 15, 2023; Previous version (with five additional DBZ pseudoprimes): Aug. 2, 2023.
Appeared in INTEGERS, v. 23 (2023), #A95.
This version: Oct. 13, 2023 (adding the DBKauers 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 pseudoprimes, rather, like in the cases of Perrin pseudoprimes and the famous
Carmichael primes, proving the mere existence of infinitely many of them.
Added March 26, 2024:
Read JeanPaul Delahaye's fascinating column (
Pour La Science, April 2024). [en Francais, but you can click on "English"] and here is the
.pdf version
C programs
See Robert DB's github site
Maple packages

Perrin.txt,
a Maple package to generate lots of Perrinstyle Primality tests

PerrinVV.txt,
a Maple package to generate lots of Perrinstyle Primality tests inspired by Vince Vatter's
beautiful combinatorial proof of the Perrin property, and the EdlinZeilberger extension of the
GouldenJackson cluster method. It is really depricated, since in hindsight it is simpler to use
the general Cfinite ansatz. It is mainly here for old time's sake.
Sample Input and Output for Perrin.txt

If you want to see all the Perrinlike primality tests where there is only one pseudoprime 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 pseudoprimes <=10000 for, 2<=k<=7, 1<=N<=7, along with the pseudoprimes <=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 pseudoprimes <=1000 for, 2<=k<=7, 1<=N<=7, along with the pseudoprimes <=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 Pseudoprimes less than a million (two of them)
the input file
yields the output file

If you want to see the see all the Pseudoprimes 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 Pseudoprimes 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 Pseudoprimes 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 Lucastype Primality tests, along with their associated pseudoprimes 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 (32*ss^2)/(1ss^2s^3), pseudoprimes:
182, 25201, 54289, 63618)
the input file
yields the output file

If you want to see the see all the Perrintype Primality tests, along with their associated pseudoprimes 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 Perrintype Primality tests, along with their associated pseudoprimes 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
Doron Zeilberger's Home Page
Robert DoughertyBliss 's Home Page