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