Perrin's remarkable sequence

Stan Wagon&JoanHutchinson wagon at
Mon May 18 00:01:06 CEST 1998

>>>Note that the result states "if n is prime, then n divides a(n)".  The=

converse is not true.

Yes, but it is quite remarkable that the first counterexample is very
large...over 200,000. The references in Shallit's book contain a wealth o=
information about Perrin sequences, and it does seem possible that, upon
some different choice of parameters, one might find a Perrin-like sequenc=
that is as good as the Lucas sequence in common use. By this I mean that =
one combines a 2-strong pseudoprime test and a 3-strong-pseudoprime test
with a Lucas test then there are no counterexamples under 10^16. It would=

be nice to find a Perrin-type sequence with this property too, but I have=

not yet.

Let me add that a chapter in my forthcoming book, Mathematica in Action,
goes into the Perrin and Lucas sequences in quite a bit of detail,
providing Mathematica code to make it easy to check other parameter value=

stan wagon
macalester college

More information about the SeqFan mailing list