From: pmontgom@cwi.nl (Peter L. Montgomery)
Subject: Re: Extended Fibonacci Series
Date: Fri, 28 May 1999 06:00:56 GMT
Newsgroups: sci.math
Keywords: Properties of the Perrin sequence, references
In article <7idn1k$djp$1@front6m.grolier.fr>
"panh" writes:
>Dave Rusin a écrit dans le message :
>7ib02s$im0$1@gannett.math.niu.edu...
>> Dave Rusin on 15 May 1999 at 01:26.4 GMT
>> > You're missing the really nice sequence of this type: Suppose
>> > a_n = a_{n-2} + a_{n-3} (that is, if you proceed rabbit-like but with
>> > a longer gestational period :-) ) beginning with a1=0, a2=2, a3=3.
>> > You'll notice from computations that n is prime iff n divides a_n.
>Can you explain the proof of:
>If n is prime then n divides a_n.
>thank you.
Let x1, x2, x3 be the roots of X^3 = X + 1.
Equating coefficients in the polynomial identity
(X - x1) * (X - x2) * (X - x3) = X^3 - X - 1
we find
x1 + x2 + x3 = 0
x1*x2 + x1*x3 + x2*x3 = -1
x1*x2*x3 = 1
Then we calculate
x1^2 + x2^2 + x3^2
= (x1 + x2 + x3)^2 - 2 (x1*x2 + x1*x3 + x2*x3)
= 0^2 - 2*(-1) = 2 = a2
and
x1^3 + x2^3 + x3^3
= 3 x1*x2*x3
+ (x1 + x2 + x3)*(x1^2 + x2^2 + x3^2 - x1*x2 - x1*x3 - x2*x3)
= 3 + 0 = a3
An induction proof confirms that
a[n] = x1^n + x2^n + x3^n
for all integer n >= 1.
Now suppose n = p is prime.
Equate coefficients of X^(2p) in the polynomial identity
(X^p - x1^p)*(X^p - x2^p)*(X^p - x3^p)
== (X - x1)^p * (X - x2)^p * (X - x3)^p
== (X^3 - X - 1)^p
== X^(3p) - X^p - 1 (mod p)
The result is a[p] == 0 (mod p).
[x1, x2, x3 are algebraic integers -- the congruences
are over the ring of algebraic integers divisible by p.]
Daniel Shanks et al had an article about this sequence in
Mathematics of Computation about 10 years ago. As I recall,
the converse is false -- there exist non-prime value of n
for which n divides a[n]. Otherwise we would have
a polynomial-time primality test.
--
Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California
Microsoft Research and CWI
==============================================================================
From: reznick@mimas.math.uiuc.edu (Bruce Reznick)
Subject: Re: A remarkable sequence
Date: 27 May 1999 17:43:59 GMT
Newsgroups: sci.math
Let me make two immodest additions to this discussion of the
Stern sequence. In my paper "Some binary partition functions", which
appeared in the collection "Analytic number theory" (Allerton Park,
IL, 1989), 451--477, Progr. Math., 85, Birkhäuser Boston, Boston, MA,
1990. MR 91k:11092, I discussed a variety of questions regarding the
number of ways to write n = \sum_j a_j2^j, when a_j \in {0,1,...,d-1}.
The Stern sequence corresponds to d = 3. An old Putnam problem amounts
to d = 4.
It is easy to show that in the sequence 1 1 2 1 3 2 3 1 4 3..,
every third element of the sequence is even. This begs the question of
the distribution of the Stern sequence modulo m for m > 2. I've made
some progress in this direction and gave a talk at the March 1999 AMS
Meeting in Urbana. (See abstract 941-11-279 in a recent Abstracts of
the AMS.) In short, consecutive pairs of the Stern sequence are as
equidistributed mod m as they can be, given that they are
relatively prime. One consequence is that the probability that a prime
p divides s(n) is asymptotically 1/(p+1). I hope to finish writing
this paper this summer, and will be happy to send a preprint to anyone
interested.
Bruce Reznick
==============================================================================
From: Jpr2718@aol.com
Subject: Perrin Pseudoprimes
Date: Mon, 24 May 1999 22:10:25 EDT
Newsgroups: [missing]
To: rusin@vesuvius.math.niu.edu
Dear Professor Rusin,
In regard to the Perrin sequence, you wrote, "This sequence came up in the
problem section of the American Mathematical Monthly about five years ago."
Do you have a more precise reference?
The current issue (Vol 30, No 3, May 1999) of the College Math Journal has
this as Problem 653 (page 230). I am sure the editors know this problem
appears in the literature, but I am planning to send a list of references,
and I would like to include any appearances in the American Mathematical
Monthly. Plus, I am interested in seeing how it was treated in the Monthly.
The Monthly also ran the problem (that x_p is divisible by p) in 1908,
proposed and solved by E. B. Escott, with a second, more general, solution by
no less than L. E. Dickson. (Volume 15, 1908, Problem 151, proposal on page
22, solutions on pages 187 and 209. Note solutions less than a year from
problem proposal! Also, Escott asked whether any composite n divided x_n,
but this was not solved in 1908.)
Problem 10655 in the April 1998 Monthly, Vol. 105, No. 4. is: Define a
sequence x_0, x_1, x_2, ... by x_0 = 4, x_1 = x_2 = 0, x_3 = 3, and x_m+4 =
x_m+1 + x_m for m >= 0. Prove that x_p is divisible by p for every prime p.
Ian Stewart wrote about the Perrin sequence in his June 1996 Mathematical
Recreations column in Scientific American, with partial corrections in
November.
Some other references (that you might already be aware of):
G.C. Kurtz, Daniel Shanks, and H.C. Williams, "Fast Primality Tests for
Numbers Less Than 50x10^9," Mathematics of Computation, Volume 46, Number
174, April 1986, Pages 691-701.
Steven Arno, "A Note on Perrin Pseudoprimes," Mathematics of Computation,
Volume 56, Number 193, January 1991, Pages 371-376.
William Adams and Daniel Shanks, " Strong Primality Tests That Are Not
Sufficient," Mathematics of Computation, Volume 39, Number 159, July 1982,
Pages 255-300.
William W. Adams, "Characterizing Pseudoprimes for Third-Order Linear
Recurrences," Mathematics of Computation, Volume 48, Number 177, January
1987, Pages 1-15.
John Robertson
==============================================================================
From: Dave Rusin
Subject: Re: Perrin Pseudoprimes
Date: Wed, 26 May 1999 15:06:46 -0500 (CDT)
Newsgroups: [missing]
To: Jpr2718@aol.com
>In regard to the Perrin sequence, you wrote, "This sequence came up in the
>problem section of the American Mathematical Monthly about five years ago."
>Do you have a more precise reference?
Problem #10268, 1992 (Solution June 1995).
Thank you for sending the long list of references to this problem; I hadn't
seen most of them. The solution in the Monthly issue listed above has
what appear to be some additional references.
It's kind of nice seeing the topic arise again 100 years after Perrin's
first treatment!
dave