Nombre de Perrin

En mathématiques, un nombre de Perrin est un terme de la suite de Perrin, variante de la suite de Padovan. Cette suite d'entiers est définie par récurrence par :

P(0) = 3, P(1) = 0, P(2) = 2 et pour tout n ≥ 3, P(n) = P(n − 2) + P(n − 3).

Les 20 premiers termes sont[1] :

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
P(n)	3	0	2	3	2	5	5	7	10	12	17	22	29	39	51	68	90	119	158	209

Primalité

Si n est un nombre premier alors P(n) est un multiple de n.

François Olivier Raoul Perrin avait conjecturé la réciproque en 1899. Cependant, le premier contre-exemple n > 1 a été trouvé en 1980 : il s'agit de 271 441. En effet, 271 441 divise P(271 441) mais 271 441 = 521². Le nombre P(271 441) a 33 150 chiffres. Le nombre 271 441 est un nombre pseudo-premier de Perrin[2]. Il y en a une infinité[3].

Les nombres de Perrin premiers forment la suite A074788 de l'OEIS, et leurs indices la suite A112881.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Perrin number » (voir la liste des auteurs).

Suite A001608 de l'OEIS.
Suite A013998 de l'OEIS.
(en) Jon Grantham, « There are infinitely many Perrin pseudoprimes », J. Number Theory, vol. 130, n^o 5,‎ 2010, p. 1117-1128 (DOI 10.1016/j.jnt.2009.11.008, lire en ligne).

Voir aussi

Bibliographie

(en) William Adams et Daniel Shanks, « Strong primality tests that are not sufficient », Math. Comput., vol. 39, n^o 159,‎ 1982, p. 255-300 (DOI 10.2307/2007637, JSTOR 2007637, Math Reviews 0658231)
(en) Zoltán Füredi (de), « The number of maximal independent sets in connected graphs », Journal of Graph Theory, vol. 11, n^o 4,‎ 1987, p. 463-470 (DOI 10.1002/jgt.3190110403)
(en) Donald E. Knuth, The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley, 2011 (ISBN 978-0-201-03804-0 et 0-201-03804-8)
Édouard Lucas, « Théorie des fonctions numériques simplement périodiques », Amer. J. Math., vol. 1, n^o 3,‎ 1878, p. 197-240 (DOI 10.2307/2369311, JSTOR 2369311)
(en) R. Perrin, « Question 1484 », L'Intermédiaire des mathématiciens, vol. 6,‎ 1899, p. 76

Liens externes

Lionel Fourquaux, « Construction de nombres pseudo-premiers de Perrin », sur normalesup.org, août 2015
(en) Eric W. Weisstein, « Perrin Sequence », sur MathWorld
(en) Eric W. Weisstein, « Perrin Pseudoprime », sur MathWorld
(es) Séquence et fichiers avec séquence (en espagnol)

Portail de l'analyse

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Suite A001608 de l'OEIS.

[2] Suite A013998 de l'OEIS.

[3] (en) Jon Grantham, « There are infinitely many Perrin pseudoprimes », J. Number Theory, vol. 130, n^o 5,‎ 2010, p. 1117-1128 (DOI 10.1016/j.jnt.2009.11.008, lire en ligne).