Número de Perrin

Erro al crear miniatura:

Espiral de triànguls equiláteros en costats que seguixen la seqüència de Perrin.

En matemàtiques, els números de Perrin estan definits per la relació de recurrencia:

P(0) = 3, P(1) = 0, P(2) = 2,

i

P(n) = P(n − 2) + P(n − 3) si n > 2.

La série comença

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39... Plantilla:OEIS

Considere's n per a la qual n dividix P(n). El resultat és

n= 1, 2, 3, 5, 7, 11, 13, ...

o siga, 1 seguit de número primo. Ha segut provat que para tots els primers p, p dividix P(p).

El recíproc no és cert. Dits número compuesto n són cridats Pseudoprimos de Perrin, sent el menor 271441 = 521².

Història

La seqüència va ser analisada per Édouard Lucas en 1878 (American Journal of Mathematics, vol 1, pàgina 230ff). En 1899 la mateixa seqüència va ser estudiada per R. Perrin (L'Intermédiaire dones Mathematiciens). L'estudi més llarc d'esta seqüència va ser realisat per Donen Shanks i Bill Adams en 1982 (Mathematics of Computation, vol 39, n. 159).

Funció generadora

La funció generadora de la seqüència de Perrin és:

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

Referències

• (2011) The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley. ISBN 0201038048.