Perrin number

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

[edit intro]

The Perrin numbers are defined by the recurrence relation

$P_n := \begin{cases} 3 & \mbox{if } n = 0; \\ 0 & \mbox{if } n = 1; \\ 2 & \mbox{if } n = 2; \\ P_{n-2}+P_{n-3} & \mbox{if } n > 2. \\ \end{cases}$

The first few numbers of the sequence are: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, ...

Properties

A special property of the sequence of Perrin numbers is, that if $p\$ is a prime number, then $p\$ divides $P_p\$ . The converse is false, because there exist composite numbers $q\$ which divide $P_q\$ . Those numbers $q\$ are called Perrin pseudoprimes. The first few Perrin pseudoprimes are: 271441, 904631, 16532714, 24658561, 27422714, ...