Perrin number

Perrin number

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 ... OEIS|id=A001608

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

History

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

Generating function

The generating function of the Perrin sequence is

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

Matrix form

: egin{pmatrix} 0 & 1 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 end{pmatrix}^n egin{pmatrix} 2 \ 0 \ 3 end{pmatrix} = egin{pmatrix} Pleft(n+2 ight) \ Pleft(n+1 ight) \ Pleft(n ight) end{pmatrix}

Binet-like formula

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

: x^3 -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

:Pleft(n ight) = {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

:Pleft(n ight) 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.

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 :egin{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^nend{matrix}

which gives us three linear equations with coefficients over the splitting field of x^3 -x -1 ; by inverting a matrix we can solve for p^n, q^n, r^n and then we can raise them to the "k"th 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:

egin{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 ight)\23G(3n)& = &left(3u^3 + 2v^3 + 3w^3 - 3(uv^2 + uw^2 + vw^2 + vu^2) + 6v^2w + 18uvw ight) \23G(3n+1)& = &left(v^3-w^3+6uv^2+9uw^2+6vw^2+9vu^2-3wu^2+6wv^2-6uvw ight) 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(log n) multiplies.

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 [OEIS|id=A013998] ; Jon Grantham has proved [ [http://www.pseudoprime.com/pseudo3.pdf There are infinitely many Perrin pseudoprimes] , Jon Grantham, unpublished manuscript.] that there are infinitely many Perrin pseudoprimes.

A Perrin prime is a Perrin number that is prime. The first few Perrin primes are OEIS|id=A074788:

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

Notes

References

*cite journal
author = Adams, William; Shanks, Daniel
title = Strong primality tests that are not sufficient
journal = Mathematics of Computation
volume = 39
year = 1982
issue = 159
pages = 255–300
id = MathSciNet | id = 0658231
doi = 10.2307/2007637

*cite journal
author = Füredi, Z.
title = The number of maximal independent sets in connected graphs
journal = Journal of Graph Theory
volume = 11
issue = 4
year = 1987
pages = 463–470
doi = 10.1002/jgt.3190110403

*cite journal
author = Lucas, E.
authorlink = Edouard Lucas
title = Théorie des fonctions numériques simplement périodiques
journal = American Journal of Mathematics
volume = 1
pages = 197–240
year = 1878
doi = 10.2307/2369311

*cite journal
author = Perrin, R.
title = Query 1484
journal = L'Intermediaire Des Mathematiciens
volume = 6
pages = 76
year = 1899

External links

* [http://www.ai.univie.ac.at/perrin.html Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence]
* [http://www.mathpages.com/home/kmath127.htm MathPages - Lucas Pseudoprimes]
* [http://www.mathpages.com/home/kmath345.htm MathPages - Perrin's Sequence]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Perrin — General= Perrin may refer to: *Perrin Air Force Base, located in rural Grayson County, Texas *Perrin friction factors, in hydrodynamics *Perrin number, in mathematics *Perrin s Beaked Whale, the newest species of Beaked Whale to be described… …   Wikipedia

  • Perrin Aybara — Perrin t Bashere Aybara, or Goldeneyes , is one of the main characters of Robert Jordan s epic fantasy The Wheel of Time .DescriptionPerrin is stocky with the thick arms and shoulders of a blacksmith. He has curly brown hair. His eyes were dark… …   Wikipedia

  • Perrin's beaked whale — Size comparison against an average human Conservation status …   Wikipedia

  • Perrin, Texas — Perrin is an unincorporated community in southeastern Jack County, Texas, United States). It has a population of approximately 300, and is located at the cross roads of HWY 281 and FM 2210It was established in 1804 by Levi Perrin (ref. Mrs. Crow …   Wikipedia

  • Perrin's Beaked Whale — Taxobox name = Perrin s Beaked Whale image2 width= 240px image2 caption = Size comparison against an average human status = NE status system = iucn3.1 regnum = Animalia phylum = Chordata classis = Mammalia ordo = Cetacea subordo = Odontoceti… …   Wikipedia

  • Perrin-Folge — Die Perrin Folge ist eine Folge natürlicher Zahlen, bei der, ähnlich wie bei der Fibonacci Folge, jedes Glied die Summe von Vorgängergliedern ist (also eine rekursiv definierte Folge). Inhaltsverzeichnis 1 Geschichte 2 Definition 3… …   Deutsch Wikipedia

  • Perrin , Jean Baptiste — (1870–1942) French physicist Perrin was born in Lille, France, the son of an army officer. He was educated at the Ecole Normale, where he received his doctorate in 1897. He was appointed to the Sorbonne where he was made professor of physical… …   Scientists

  • Perrin, Jean — (1870 1942)    physicist, Nobel laureate    Born in Lille, Jean Perrin was one of the promoters of atomic theory, although more from the conceptual than the experimental viewpoint. His studies (1895) proving that cathodic rays are constituted of… …   France. A reference guide from Renaissance to the Present

  • 12 (number) — ← 11 13 → 12 ← 10 11 12 13 14 15 16 …   Wikipedia

  • 17 (number) — ← 16 18 → 17 ← 10 11 12 13 14 15 16 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”