## Most recent change of PerrinSequence

Edit made on June 10, 2013 by ColinWright at 09:30:46

Deleted text in red / Inserted text in green

WW WM
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: EQN:P(n)=\alpha^n+\beta^n+\gamma^n where EQN:\alpha
EQN:\beta and EQN:\gamma are the solutions to the cubic equation EQN: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 EQN:\beta and EQN:\gamma to have be the solutions with modulus less than 1,
this gives [[[> EQN:\alpha\approx1.32471795976162... ]]] EQN:P(n)\approx\alpha^n,
EQN:P(n)\approx\alpha^n where EQN:\alpha\approx1.32471795976162 and so the sequence exhibits exponential growth.

Taking EQN:log_{10}(\alpha)=0.1221234... Since the EQN:n^{th} term is roughly EQN:\alpha^n, we can take log base ten
and
see that the EQN:log_{10}(\alpha)=0.1221234... and so EQN:n^{th} term will
have roughly /0.12n/ EQN:0.12n decimal digits. Thus the sequence exhibits exponential growth.

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 ...
COLUMN_START
| /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 |
COLUMN_SPLIT
| /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 |
COLUMN_SPLIT
| /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 |
COLUMN_END

----
* http://en.wikipedia.org/wiki/Perrin_number
* http://mathworld.wolfram.com/PerrinSequence.html