Perrin number

From Wikipedia, the free encyclopedia

In mathematics, the Perrin numbers are defined by the recurrence relation

P(0) = 3, P(1) = 0, P(2) = 2,

and

P(n) = P(n − 2) + P(n − 3) for n > 2.

The series begins

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... (sequence A001608 in OEIS)

The number of different maximal independent sets in an n-vertex cycle graph is counted by the nth Perrin number (Füredi 1987).

Contents

[edit] History

This sequence was analyzed by Edouard Lucas (1878). In 1899, the same sequence was mentioned by R. Perrin. The most extensive treatment of this sequence was given by Adams and Shanks (1982).

[edit] Generating function

The generating function of the Perrin sequence is

G(P(n);x)=\frac{3-x^2}{1-x^2-x^3}.

[edit] Matrix form

\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n \begin{pmatrix} 2 \\ 0 \\ 3 \end{pmatrix} = \begin{pmatrix} P\left(n+2\right) \\ P\left(n+1\right) \\ P\left(n\right) \end{pmatrix}

[edit] Binet-like formula

The Perrin sequence numbers can be written in terms of powers of the roots of the equation

x3 − x − 1 = 0.

This equation has 3 roots; one real root p (known as the plastic number) and two complex conjugate roots q and r. Given these three roots, the Perrin sequence analogue of the Fibonacci sequence Binet formula is

P\left(n\right) = {p^n} + {q^n} + {r^n}.

Since the magnitudes of the complex roots q and r are both less than 1, the powers of these roots approach 0 for large n. For large n the formula reduces to

P\left(n\right) \approx {p^n}

This formula can be used to quickly calculate values of the Perrin sequence for large n. The ratio of successive terms in the Perrin sequence approaches p, a.k.a. the plastic number, which has a value of approximately 1.324718. This constant bears the same relationship to the Perrin sequence and the Padovan sequence as the golden ratio does to the Fibonacci sequence and the silver ratio does to the Pell numbers.

[edit] Multiplication formula

From the Binet formula, we can obtain a formula for G(kn) in terms of G(n−1), G(n) and G(n+1); we know

\begin{matrix} G(n-1) & = &p^{-1}p^n + &q^{-1}q^n +& r^{-1} r^n\\ G(n) & =& p^n+&q^n+&r^n\\ G(n+1) &=& pp^n +& qq^n +& rr^n\end{matrix}

which gives us three linear equations with coefficients over the splitting field of x3 − x − 1; by inverting a matrix we can solve for pn,qn,rn and then we can raise them to the kth power and compute the sum.

Example magma code:

P<x> := PolynomialRing(Rationals());
S<t> := SplittingField(x^3-x-1); 
P2<y> := PolynomialRing(S);
p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]);
Mi:=Matrix(1/p,1/q,1/r,[1,1,1],p,q,r)^(-1);
T<u,v,w> := PolynomialRing(S,3);
v1 := ChangeRing(Mi,T) *Matrix(u,[v],w);
[p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in -1..1;

with the result that, if we have u = G(n − 1),v = G(n),w = G(n + 1), then

\begin{matrix} 23G(2n-1) &=& 4u^2 + 3v^2 + 9w^2 + 18uv - 12uw - 4vw \\ 23G(2n) &=& 18uw - 4uv + 6vw - 6u^2 + 7v^2 - 2w^2\\ 23G(2n+1) &=& 9u^2 + v^2 + 3w^2 + 6uv - 4uw - 14vw \\ 23G(3n-1)& = &\left(-4u^3 + 2v^3 -w^3 + 9(uv^2+vw^2+wu^2) + 3v^2w+6uvw\right)\\ 23G(3n)& = &\left(3u^3 + 2v^3 + 3w^3 - 3(uv^2 + uw^2 + vw^2 + vu^2) + 6v^2w + 18uvw\right) \\ 23G(3n+1)& = &\left(v^3-w^3+6uv^2+9uw^2+6vw^2+9vu^2-3wu^2+6wv^2-6uvw\right) \end{matrix}

The number 23 here arises from the discriminant of the defining polynomial of the sequence.

This allows you to compute the nth Perrin number using integer arithmetic in O(logn) multiplies.

[edit] Primes and divisibility

Consider n for which n divides P(n). Those are

n = 1, 2, 3, 5, 7, 11, 13, ...

that is, initially 1 followed by prime numbers. It has been proven that for all primes p, p divides P(p). However, the converse is not true: for some composite numbers n, n may still divide P(n). If n has this property, it is called a Perrin pseudoprime. The question of the existence of Perrin pseudoprimes was considered by Perrin himself, but it was not known whether they existed until Adams and Shanks (1982) discovered the smallest one, 271441 = 5212; the next-smallest is 904631 = 7 x 13 x 9941. There are seventeen of them less than a billion [1]; Jon Grantham has proved [2] that there are infinitely many Perrin pseudoprimes.

A Perrin prime is a Perrin number that is prime. The first few Perrin primes are (sequence A074788 in OEIS):

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797

E. W. Weisstein found a 32,147 digit probable Perrin prime in May 2006, Perrin(263226).

[edit] Notes

  1. ^ (sequence A013998 in OEIS)
  2. ^ There are infinitely many Perrin pseudoprimes, J. Perrin, unpublished manuscript.

[edit] References

  • Adams, William; Shanks, Daniel (1982). "Strong primality tests that are not sufficient". Mathematics of Computation 39 (159): 255–300. doi:10.2307/2007637. MR0658231. 
  • Füredi, Z. (1987). "The number of maximal independent sets in connected graphs". Journal of Graph Theory 11 (4): 463–470. doi:10.1002/jgt.3190110403. 
  • Lucas, E. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics 1: 197–240. doi:10.2307/2369311. 
  • Perrin, R. (1899). "Query 1484". L'Intermediaire Des Mathematiciens 6: 76. 

[edit] External links

Languages