Perrin number

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

P (n) = P (n - 2) + P (n - 3)

for

n > 2

with initial values

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

The sequence of Perrin numbers starts with

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

The number of different maximal independent sets in an $n$ -vertex cycle graph is counted by the $n$ th Perrin number for $n > 1$ .^[1]

History

This sequence was mentioned implicitly by Édouard Lucas (1876). In 1899, the same sequence was mentioned explicitly by François Olivier Raoul Perrin.^[2] The most extensive treatment of this sequence was given by Adams and Shanks (1982).

Properties

Generating function

The generating function of the Perrin sequence is

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

Matrix formula

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(n\right)\\P\left(n+1\right)\\P\left(n+2\right)\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 Lucas 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 as the golden ratio does to the Lucas sequence. Similar connections exist also between p and the Padovan sequence, between the golden ratio and Fibonacci numbers, and between the silver ratio and 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

{\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 $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 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)&=&-6u^{2}+7v^{2}-2w^{2}-4uv+18uw+6vw\\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^{2}w+6uvw\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+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(\log n)$ multiplies.

Primes and divisibility

Perrin pseudoprimes

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 first few Perrin pseudoprimes are

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (sequence A013998 in the OEIS)

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 = 521²; the next-smallest is 904631 = 7 x 13 x 9941. There are seventeen of them less than a billion;^[3] Jon Grantham has proved^[4] that there are infinitely many Perrin pseudoprimes.

Adams and Shanks (1982) noted that primes also meet the condition that P(-p) = -1 mod p. Composites where both properties hold are called Restricted Perrin pseudoprimes (sequence A018187 in the OEIS). Further conditions can be applied using the six element signature of n which must be one of three forms.

While Perrin pseudoprimes are rare, they have significant overlap with Fermat pseudoprimes. This contrasts with the Lucas pseudoprimes which are anti-correlated. The latter condition is exploited to yield the popular, efficient, and more effective BPSW test which has no known pseudoprimes, and the smallest is known to be greater than 2⁶⁴.

Perrin primes

A Perrin prime is a Perrin number that is prime. The first few Perrin primes are:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... (sequence A074788 in the OEIS)

For these Perrin primes, the index $n$ of $P (n)$ is

2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, ... (sequence A112881 in the OEIS)

Notes

↑ Füredi (1987)
↑ Knuth (2011)
↑ (sequence A013998 in the OEIS)
↑ Jon Grantham (2010). "There are infinitely many Perrin pseudoprimes" (PDF). Journal of Number Theory. 130 (5): 1117–1128. doi:10.1016/j.jnt.2009.11.008.

References

Adams, William; Shanks, Daniel (1982). "Strong primality tests that are not sufficient". Mathematics of Computation. American Mathematical Society. 39 (159): 255–300. doi:10.2307/2007637. JSTOR 2007637. MR 0658231.

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.

Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. ISBN 0201038048.
Lucas, E. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics. The Johns Hopkins University Press. 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311.

Perrin, R. (1899). "Query 1484". L'Intermédiaire des Mathématiciens. 6: 76.

External links

Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin

By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient

Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin

Patterns	Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap

First 50 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229

List of prime numbers

Classes of natural numbers

Powers and
related numbers

Of the form
a × 2^b ± 1

Other polynomial
numbers

Recursively defined
numbers

Possessing a
specific set
of other numbers

Expressible via
specific sums

Generated
via a sieve

Lucky

Code related

Meertens

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star

non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral

non-centered	Tetrahedral Octahedral Dodecahedral Icosahedral Stella octangula

pyramidal	Square pyramidal Pentagonal pyramidal Hexagonal pyramidal Heptagonal pyramidal

4-dimensional

centered	Centered pentachoric Squared triangular

non-centered	Pentatope

Pseudoprimes

Combinatorial
numbers

Arithmetic functions

By properties of σ(n)	Abundant Almost perfect Arithmetic Colossally abundant Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical number Primitive abundant Quasiperfect Refactorable Sublime Superabundant Superior highly composite Superperfect

By properties of Ω(n)	Almost prime Semiprime

By properties of φ(n)	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient

By properties of s(n)	Amicable Betrothed Deficient Semiperfect

Dividing a quotient

Other prime factor
or divisor related
numbers

Recreational
mathematics

Base-dependent
numbers

This article is issued from Wikipedia - version of the 9/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.