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. > > > > >