From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: A recursive sequence
Date: 6 Sep 1996 18:35:34 GMT
In article <3230662E.4BFE@po.cwru.edu>,
Charles Wells wrote:
>I recently ran across a reference to the following recursively
>defined sequence:
>
>f[0] = 3
>f[1] = 0
>f[2] = 2
>f[n] = f[n-2]+f[n-3]
>
>The reference mentioned the conjecture that n divides f[n] if and
>only if n is prime (for n>1 clearly). I have no record of where I
>saw this and would appreciate pointers to the literature.
I think it appeared in the American Mathematical Monthly about 2
years ago, although I could have sworn I saw it in the exercises of
some relatively basic number theory textbook years before that, too.
If n is prime, then, yes, n divides f[n].
This is part of a more general statement: given any sequence {a_n} determined
linear recurrence, if n is prime, then n divides ... well, not a_n,
necessarily, but rather one can find a few constants c_i depending on
the recurrence relation so that if n is prime, then n divides
c_0 a_n + c_1 a_(n-1) + ... c_k a_(n-k).
You can use this as a primality test, but there's no reason to expect
this to be an "if and only if" result. You can even increase the
success of the test by using multiple sequences (e.g. if the given
recurrence corresponds to x^3 - x - 1, use a recurrence corresponding
to the polynomial whose roots are the squares of this one's) but as
far as I can tell, for any finite number of sequences there will be
composite numbers n for which n divides the appropriate linear combinations
of the a_n.
In your example, try for example the number n = 27664033 = 3037 * 9109.
dave
==============================================================================
From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math
Subject: Re: A recursive sequence
Date: Tue, 10 Sep 1996 05:25:27 GMT
Charles Wells wrote:
> I recently ran across a reference to the following recursively
> defined sequence:
>
> f[0] = 3
> f[1] = 0
> f[2] = 2
> f[n] = f[n-2]+f[n-3]
>
> The reference mentioned the conjecture that n divides f[n] if and
> only if n is prime (for n>1 clearly). I have no record of where I
> saw this and would appreciate pointers to the literature.
This sequence was discussed by Edouard Lucas in 1878 (American Journal
of Mathematics, vol 1, page 230ff). He noted that the divisibility
property you mentioned is an immediate consequence of Fermat's Little
Theorem, and as such is a necessary but not sufficient condition for
primality. Subsequently (1899) the same sequence was mentioned by
R. Perrin (L'Intermediaire Des Mathematiciens). The most extensive
(published) treatment of this sequence was given in an excellent paper
by Dan Shanks and Bill Adams in 1982 (Mathematics of Computation, vol
39, n. 159). [Sadly, Dan Shanks passed away just last Friday at the
age of 80.] Shanks and Adams referred to this as Perrin's sequence.
This sequence has many interesting properties, making it, in some
ways, more remarkable than the Fibonacci sequence. For example,
most people are familiar with the spiral of equilateral squares
whose edge lengths correspond to the Fibonacci numbers, but less
well-known is the spiral of equilateral triangles shown (crudely)
below:
______________
/ \ / \
/ \ / \
/ \ / \
/_______\ / \
\ / \ / \
\ / \ / \
\ _______\/_____________\
\ /
\ /
\ /
\ /
\ /
\ /
\ /
\ /
\ /
A better picture of this can be found at the MathPages web site,
. The edge lengths of
successive triangles in this spiral satisfy the Perrin recurrence
s[n]=s[n-2]+s[n-3] as well as the recurrence s[n]=s[n-1]+s[n-5], as
is apparent from the above figure. This can be seen as a consequence
of the fact that the characteristic polynomial of Perrin's sequence,
x^3 - x - 1, is a divisor of the characteristic polynomial of the
5th order sequence, i.e.,
x^5 - x^4 - 1 = (x^3 - x - 1)(x^2 - x - 1)
Interestingly, the real root r of x^3 - x - 1 has the nice expression
as a sequence of nested cube roots:
___________________________
3/ ____________________
r = / 3/ _________________
\/ 1 + / 3/ _______________
\/ 1 + / 3/
\/ 1 + /
\/ 1 + ...
= 1.324717957244746...
If we define the angle q in terms of this root r as
/ -1 2/3 \
q = invcos( --- r )
\ 2 /
then the terms of the Perrin sequence can be expressed in closed
form as
n cos(nq)
s[n] = r + 2 ---------
r^(n/2)
In fact, with the appropriate provisos, we can replace n with any
complex argument z to define Perrin's function on the complex plane.
Obviously, for any positive prime p and any integer n we have
s[pn] = s[n] (mod p)
so in particular we have
s[p] = 0
(mod p)
s[-p] = -1
In addition, for any integers m,n,k we have the relation
s[mn+k] = s[m]s[m(n-1)+k] - s[-m]s[m(n-2)+k] + s[m(n-3)+k]
Which is really just a special case of a much more general class of
relations satisfied by any linear recurring sequence. (There's an
article describing these relations on the MathPages web site.) In
this particular case we have relations like
s[2n] = s[n]^2 - 2s[-n]
s[3n] = s[n]^3 - 3s[n]s[-n] + 3
and so on, as well as
s[2n+1] = s[n]s[n+1] + s[1-n]
Using these relations for s[2n] and s[2n+1] gives an efficient means
of computing s[k] via the usual binary pattern algorithm on the plus
and minus sides of the sequence. This same two-sided approach can
be extended to higher order recurrences, but it quickly becomes more
practical to use the more general one-sided relations (described in
the article "Identities for Linear Recurring Sequences" in the Number
Theory section of the MathPages web site).
Perrin's sequence also has the interesting property that its terms
are cumulative sums of the sequence itself, i.e., we have s[1]=0 and
n-5
s[n] = SUM s[k] for n > 1
k=-3
4-n
s[n] = SUM s[-k] for n < 1
k=4
The terms of Perrin's sequence can also be expressed as a function
of binomial coefficients, leading to many interesting results. For
example, it's possible to deduce that the summation
N (2N+k)!
SUM ----------------
k=0 (2N-2k)! (1+3k)!
is an integer for N=2755452, and for no smaller N.
As a compositeness test, Perrin's sequence is much stronger than the
typical 2nd order Lucas sequence. For example, the smallest symmetric
pseudoprime relative to the Fibonacci quadratic x^2 - x- 1 is 705,
whereas the smallest realtive to Perrin's cubic x^3 - x - 1 is
27664033 = (3037)(9109)
as found by Shanks and Adams (using an HP-41C calculator!).
Subsequently Shanks, G. Kurtz, and H. Williams tabulated all the
symmetric pseudoprimes relative to Perrin's sequence less than
50(10)^9. They noted that none of these pseudoprimes had the
signature of a prime p such that Perrin's polynomial is irreducible
(mod p). As far as I know the question of whether such a pseudoprime
exists is still open.
Of course, the symmetric pseudoprimes relative to any given polynomial
f(x) (defined as composite integers n such that all the symmetric
functions of the nth powers of the roots of f(x) are congruent (mod n)
to the respective symmetric functions of the 1st powers) tend to be
products of "splitting" primes, i.e., primes modulo which f(x) splits
into linear factors. Thus we can choose polynomials with arbitrarily
rare pseudoprimes by making their Galois group as large as possible
(which by Chebotarev's density theorem makes splitting primes rare).
Only 1/6 of all primes are splitting primes relative to Perrin's
cubic x^3 - x - 1 (because its group is the symmetric group S_3), but
only 1/120 of all primes are splitting primes relative to the quintic
f(x) = x^5 - x^3 - 2x^2 + 1
because its Galois group is the fully symmetric group S_5. The
smallest symmetric pseudoprime relative to this polynomial that is
the product of two splitting primes is
2258745004684033 = (27439297)(82317889)
I suspect that this is the smallest symmetric pseudoprime of any
composition relative to the quintic, but I haven't made an exhaustive
search.
___________________________________________________________
| /*\ |
| MathPages / \ http://www.seanet.com/~ksbrown/ |
|_____________/_____\_______________________________________|
==============================================================================
From: bforslun@sky.lakeheadu.ca (Bob Forslund)
Newsgroups: sci.math
Subject: Re: A recursive sequence
Date: Tue, 10 Sep 1996 00:56:02 GMT
Charles Wells wrote:
>I recently ran across a reference to the following recursively
>defined sequence:
>f[0] = 3
>f[1] = 0
>f[2] = 2
>f[n] = f[n-2]+f[n-3]
>The reference mentioned the conjecture that n divides f[n] if and
>only if n is prime (for n>1 clearly). I have no record of where I
>saw this and would appreciate pointers to the literature.
There is an article in Scientific American (July 1996 issue) in
Mathematical Recreations pp. 102-103, by Ian Stewart, entitled "Tales
of a Neglected Number". This describes the Perrin sequence A(n)
Whenever n is a prime number, it divides A(n) exactly....
A(0)=3, A(1)=0 and A(2)=2 ...
Is this what you recall?
Cheers - Bob Forslund
email: bforslun@sky.lakeheadu.ca
==============================================================================
From: Assoc Prof W David Joyner
Newsgroups: sci.math
Subject: Re: Perrin's sequence
Date: Fri, 27 Sep 1996 06:27:35 -0400
On 26 Sep 1996, Saouter Yannick wrote:
>
> Hello,
> I am currently seeking any pointer to the proof of the fact that
> Perrin's sequence is effectively a pseudo-primality test.
> This sequence is defined by a[n+3]=a[n+1]+a[n] with initial
> values that I cannot remember for the time being. In his
...
I'm not sure if this helps but there are I think
2 more recent articles on these sequences in the
literature. There is a fairly recent one by S Arno
in Math Comp. I don't remember the date. I think there
was a recent (in the last 2 years) article in Sci American
on it with references as well (I'm told there were some
errors in that article but I've not seen it).
- David Joyner
> signature of some following terms of the sequence and
> classified the primes in three types according their
> signature but still does not give the proof of the
> initial property. Moreover he exhibits some other
> sequence having the same kind of property.
>
> What I am looking for is the proof of the original
> property. Any help would be greatfully appreciated.
>
> Yannick Saouter.
>
>
>
>
>