Perrin number

The generating function of the Perrin sequence is

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

${\displaystyle {\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}}}$

Spiral of equilateral triangles with side lengths which follow the Perrin sequence.

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

${\displaystyle 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

${\displaystyle P(n)=p^{n}+q^{n}+r^{n}.}$

Since the absolute values 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

${\displaystyle P(n)\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.

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

${\displaystyle {\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 ${\displaystyle x^{3}-x-1}$; by inverting a matrix we can solve for ${\displaystyle 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 ${\displaystyle u=G(n-1),v=G(n),w=G(n+1)}$, then

${\displaystyle {\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 computation of the nth Perrin number using integer arithmetic in ${\displaystyle O(\log n)}$ multiplies.

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 × 13 × 9941. There are seventeen of them less than a billion;[3] Jon Grantham has proved that there are infinitely many Perrin pseudoprimes.[4]

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 (e.g. OEIS: A275612 and OEIS: A275613).

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

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)

Generating P(n) where n is a negative integer yields a similar property regarding primality: if n is a negative, then P(n) is prime when P(n) mod −n = −n − 1. The following sequence represents P(n) for all n that are negative integers:

−1, 1, 2, −3, 4, −2, −1, 5, −7, 6, −1, −6, 12, −13, 7, 5, −18, 25, −20, 2, 23, −43, 45, −22, −21, 66, −88, 67, −1, ... (sequence A078712 in the OEIS)