Suite de Perrin

En mathématiques, la suite de Perrin est une variante de la suite de Padovan, de même relation de récurrence. Cette suite d'entiers est définie par récurrence par :

P_{0}=3,P_{1}=0,P_{2}=2

et pour tout

n\geqslant 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 la suite de Perrin qui sont 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, MR 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) Suite et fichiers avec suite (en espagnol)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.