Suite de Perrin

variante de la suite de Padovan

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 de la suite de Perrin à l'aide de triangles équilatéraux, utilisant la relation . Le nombre dans chaque triangle désigne la longueur de ses côtés.

Construction géométrique

modifier

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

modifier

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 , d'où la formule

Comme , on en déduit que et ,

ainsi que est l'entier le plus proche de , à partir de [1].

Propriétés

modifier

et

.
  • Fonction génératrice :
  • Expression à l'aide de coefficients binomiaux pour [2] :
Texte de Perrin dans l'intermédiaire des mathématiciens.

Utilisation comme test de primalité

modifier

Dans une question posée en 1899 dans l'intermédiaire des mathématiciens[3], 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 :

Si n est un nombre premier alors est divisible par n.

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[4] : 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é[5].

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

Démonstration du théorème de divisibilité

modifier

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[6], utilisée ici avec la matrice .

Une autre démonstration, 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 : disposition de convives avec distanciation physique

modifier

Description

modifier

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 [7].

Application

modifier

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).

Autres dispositions "covidiennes"

modifier

Le nombre de dispositions maximales de convives vérifiant la propriété de distanciation à rotation de la table (supposée circulaire) près, forme la suite définie par , où est l'indicatrice d'Euler[2]. Par exemple, pour six convives les cinq dispositions vues ci-dessus, ne sont plus que deux à rotation près. Les dix premiers termes de la suite sont : 0, 1, 1, 1, 1, 2, 1, 2, 2, 3 ; suite A127687 de l'OEIS.

Le nombre de dispositions maximales vérifiant la propriété de distanciation où les personnes sont cette fois disposées en ligne est égal à est la suite de Padovan[2]. Par exemple, pour , il y a 01010, 10010, 01001 et 10101 en notant 0 pour une place vide et 1 pour une place occupée.

Notes et références

modifier
(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).
  1. a et b J. P. Delahaye, « Des nombres premiers aux pseudo-premiers », Pour la Science, no 558,‎ , p. 80-85 (lire en ligne Accès payant)
  2. a b c et d Claude Morin, « Suites de Perrin et de Padovan », Bulletin de l’Union des Professeurs de classes préparatoires Scientifiques, no 286,‎ , p. 39-41 (lire en ligne)
  3. R. Perrin, « Question 1484 », L'Intermédiaire des mathématiciens, vol. 6,‎ , p. 76 (lire en ligne)
  4. (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)
  5. (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).
  6. Francinou, Gianella, Nicolas, Oraux X-Ens, Algèbre 1, Cassini, , exercice 7.14
  7. (en) Vincent Vatter, « Social Distancing, Primes, and Perrin Numbers », Math horizons, vol. 29, no 1,‎ , p. 5-7 (lire en ligne Accès libre)

Voir aussi

modifier

Bibliographie

modifier

Liens externes

modifier