The Perrin Sequence is the integer sequence defined by

• P(1)=0
• P(2)=2
• P(3)=3
• P(n)=P(n-2)+P(n-3)
There is a closed form formula: $P(n)=\alpha^n+\beta^n+\gamma^n$ where $\alpha$ $\beta$ and $\gamma$ are the solutions to the cubic equation $x^3-x-1=0.$ This has one real solution and two complex solutions which are complex conjugates, and whose modulus is less than one.

Taking $\beta$ and $\gamma$ to be the solutions with modulus less than 1, this gives
 $\alpha\approx1.32471795976162...$
$P(n)\approx\alpha^n,$ and so the sequence exhibits exponential growth.

Since the $n^{th}$ term is roughly $\alpha^n,$ we can take log base ten and see that $log_{10}(\alpha)=0.1221234...$ and so $n^{th}$ term will have roughly $0.12n$ decimal digits.

The Perrin Sequence has the amazing property that it seems that n divides P(n) if and only if n is a prime number. This conjecture seems solid, certainly holding for n up to 10^5, but it fails for n=271441. This is a great example how patterns fail for large enough cases.

Here are the first few values ...
 n P(n) Divides 1 0 Yes 2 2 Yes 3 3 Yes 4 2 No 5 5 Yes 6 5 No 7 7 Yes 8 10 No
 n P(n) Divides 9 12 No 10 17 No 11 22 Yes 12 29 No 13 39 Yes 14 51 No 15 68 No 16 90 No
 n P(n) Divides 17 119 Yes 18 158 No 19 209 Yes 20 277 No 21 367 No 22 486 No 23 644 Yes 24 853 No