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.
Added March 26, 2024:
Read Jean-Paul 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 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
Doron Zeilberger's Home Page
Robert Dougherty-Bliss 's Home Page