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 linéaire par :
- et pour tout .
Les 20 premiers termes en sont :
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
3 | 0 | 2 | 3 | 2 | 5 | 5 | 7 | 10 | 12 | 17 | 22 | 29 | 39 | 51 | 68 | 90 | 119 | 158 | 209 |
Elle forme la suite A001608 de l'OEIS.
Construction géométrique
La suite de Perrin vérifie aussi la relation de récurrence d'ordre 5 : , pour . Cette propriété est à la base de la construction en spirale ci-contre, débutant avec un triangle équilatéral de côté , un triangle équilatéral de côté tronqué d'un triangle de côté 1, puis un triangle équilatéral de côté (comparer avec la construction en triangles de la suite de Padovan).
Formule de type Binet
L'équation caractéristique de la récurrence s'écrit ; les solutions en sont le nombre plastique et deux nombres complexes conjugués .
L'expression de en fonction des trois suites de base s'écrit simplement sous la forme
Des relations , on tire où , d'où la formule
Comme , on en déduit que et ,
ainsi que où est l'entier le plus proche de , à partir de [1].
Propriétés
- Relation avec la suite de Padovan, notée ici : .
- Comme pour la suite de Fibonacci, la suite de Perrin s'obtient par puissance -ième de la matrice compagnon du polynôme caractéristique :
et
- Expression à l'aide de coefficients binomiaux pour :
Utilisation comme test de primalité
Dans une question posée en 1899 dans l'intermédiaire des mathématiciens[2], François Olivier Raoul Perrin fait référence à une question antérieure demandant si le fait que soit divisible par soit un "criterium" pour que soit premier (hypothèse chinoise populaire au XIXe siècle). On sait aujourd'hui que le nombre ne passe pas ce test connu aujourd'hui comme "test de primalité de Fermat"[1].
La suite étant définie par récurrence par , Perrin dit avoir trouvé une autre suite récurrente jouissant de la même propriété, suite portant maintenant son nom. Et en effet :
Perrin dit avoir vérifié la réciproque de cette propriété pour de grandes valeurs de n. De fait, le premier contre-exemple n'a été trouvé qu'en 1982 par Adams et Shanks[3] : il s'agit de = 271 441 : ce nombre divise mais 271 441 = 5212. Le nombre a 33 150 chiffres.
Le nombre 271 441 est le plus petit des nombres pseudo-premiers de Perrin, formant la suite A013998 de l'OEIS. Il a été prouvé en 2010 qu'il y en a une infinité[4].
Les nombres de la suite de Perrin qui sont premiers forment la suite A074788 de l'OEIS, et leurs indices la suite A112881.
Démonstration du théorème de divisibilité
Les congruences s'entendant modulo un nombre premier , la propriété est une conséquence de la propriété : valable pour toute matrice à coefficients entiers[5], utilisée ici avec la matrice .
Une démonstration possible, similaire à celle du petit théorème de Fermat consistant à écrire : , car, d'après le théorème de Lucas, pour , est la suivante.
On va démontrer que , ce qui prouvera , car .
D'après la formule du trinôme, , et l'on a pour .
Les nombres n'étant pas entiers, on va utiliser les relations coefficients racines :
On peut alors écrire :
La dernière somme s'entendant pour toutes les permutations de , elle est symétrique et s'exprime comme fonction polynomiale avec des coefficients entiers de et est donc égale à un nombre entier. Le résultat attendu s'en déduit.
Interprétation combinatoire
Inspiré par la distanciation physique imposée par l'épidémie de covid, Vincent Vatter s'est posé la question du nombre de façons de placer des convives autour d'une table comportant n chaises de sorte que deux convives aient au moins une chaise libre entre eux et qu'on ne puisse plus ajouter de convive sans violer cette condition (donc pas plus de deux chaises libres entre deux convives). Par exemple, pour , il y a cinq solutions, trois avec deux convives séparés par deux chaises et deux avec trois convives séparés par une chaise.
Il a montré que le nombre de solutions pour est égal au nombre de Perrin [6].
Considérons un convive d'une disposition à chaises. Soit ce convive a une seule chaise libre à sa droite et le nombre de dispositions valables est le nombre de dispositions à chaises (enlever mentalement la chaise du convive et la chaise libre), soit il a 2 chaises libres à sa droite et le nombre de dispositions valables est le nombre de dispositions à chaises. Les initialisations étant identiques, on obtient le résultat.
Cette interprétation combinatoire permet de retrouver la propriété de divisibilité ci-dessus (démonstration similaire à celle du petit théorème de Fermat par double dénombrement).
Supposons en effet qu'une rotation d'angle donne la même disposition qu'une disposition donnée à chaises (avec et premier). Alors, d'après le théorème de Bézout, il existe deux entiers >0 tels que , donc . La rotation d'angle donne donc la même disposition que celle de départ, ce qui fait que deux convives sont côte à côte, ce qui est absurde.
Dès qu'une disposition conforme à chaises existe, les rotations d'angle successives de cette disposition sont bien distinctes, donc est multiple de .
Notes et références
- ↑ a et b J. P. Delahaye, « Des nombres premiers aux pseudo-premiers », Pour la Science, no 558, , p. 80-85 (lire en ligne )
- ↑ R. Perrin, « Question 1484 », L'Intermédiaire des mathématiciens, vol. 6, , p. 76 (lire en ligne)
- ↑ (en) William Adams et Daniel Shanks, « Strong primality tests that are not sufficient », Math. Comput., vol. 39, no 159, , p. 255-300 (DOI 10.2307/2007637, JSTOR 2007637, lire en ligne)
- ↑ (en) Jon Grantham, « There are infinitely many Perrin pseudoprimes », J. Number Theory, vol. 130, no 5, , p. 1117-1128 (DOI 10.1016/j.jnt.2009.11.008, lire en ligne).
- ↑ Francinou, Gianella, Nicolas, Oraux X-Ens, Algèbre 1, Cassini, , exercice 7.14
- ↑ (en) Vincent Vatter, « Social Distancing, Primes, and Perrin Numbers », Math horizons, vol. 29, no 1, , p. 5-7 (lire en ligne )
Voir aussi
- Suite de Padovan
- Suite de Lucas, qui est à la suite de Fibonacci, ce qu'est la suite de Perrin à la suite de Padovan.
Bibliographie
- (en) Zoltán Füredi (de), « The number of maximal independent sets in connected graphs », Journal of Graph Theory, vol. 11, no 4, , 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, (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, no 3, , p. 197-240 (DOI 10.2307/2369311, JSTOR 2369311, lire en ligne)
Liens externes
- Lionel Fourquaux, « Construction de nombres pseudo-premiers de Perrin », sur normalesup.org,
- (en) Eric W. Weisstein, « Perrin Sequence », sur MathWorld
- (en) Eric W. Weisstein, « Perrin Pseudoprime », sur MathWorld
- (es) Suite et fichiers avec suite (en espagnol)
- Portail de l'analyse