HEADERS_END

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

this gives [[[> EQN:\alpha\approx1.32471795976162... ]]] EQN:P(n)\approx\alpha^n,

and see that

have roughly

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

* http://www.google.com/search?q=perrin+sequence