Perrin sequence

Construct a recurrence relation with initial terms $a_{0}=3$ , $a_{1}=0$ , $a_{2}=2$ and $a_{n}=a_{n-3}+a_{n-2}$ for $n>2$ . The first few terms of the sequence defined by this recurrence relation are: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367 (listed in A001608 of Sloane’s OEIS). This is the Perrin sequence, sometimes called the Ondrej Such sequence. Its generating function is

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

A number in the Perrin sequence is called a Perrin number.

It has been observed that if $n|a_{n}$ , then $n$ is a prime number, at least among the first hundred thousand integers or so. However, the square of 521 passes this test.

The $n$ th Perrin number asymptotically matches the $n$ th power of the plastic constant.

References

1 W. W. Adams and D. Shanks, “Strong primality tests that are not sufficient” Math. Comp. 39, pp. 255 - 300 (1982)

Title	Perrin sequence
Canonical name	PerrinSequence
Date of creation	2013-03-22 16:05:19
Last modified on	2013-03-22 16:05:19
Owner	Mravinci (12996)
Last modified by	Mravinci (12996)
Numerical id	5
Author	Mravinci (12996)
Entry type	Definition
Classification	msc 11B39
Defines	Perrin number