Perrin's remarkable sequence

[Stan Wagon&JoanHutchinson]

>>>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=
f
information about Perrin sequences, and it does seem possible that, upon
some different choice of parameters, one might find a Perrin-like sequenc=
e
that is as good as the Lucas sequence in common use. By this I mean that =
if
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=
s.

stan wagon
macalester college