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 :

${\displaystyle P_{0}=3,P_{1}=0,P_{2}=2}$ et pour tout ${\displaystyle n\geqslant 3,P_{n}=P_{n-2}+P_{n-3}}$.

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
${\displaystyle P_{n}}$	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 : ${\displaystyle P_{n}=P_{n-1}+P_{n-5}}$, pour ${\displaystyle n\geqslant 5}$. Cette propriété est à la base de la construction en spirale ci-contre, débutant avec un triangle équilatéral de côté ${\displaystyle P_{2}=2}$, un triangle équilatéral de côté ${\displaystyle P_{3}=3}$ tronqué d'un triangle de côté 1, puis un triangle équilatéral de côté ${\displaystyle P_{4}=2}$ (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 ${\displaystyle x^{3}-x-1=0}$ ; les solutions en sont le nombre plastique ${\displaystyle \psi ={\sqrt[{3}]{{\frac {1}{2}}+{\frac {\sqrt {69}}{18}}}}+{\sqrt[{3}]{{\frac {1}{2}}-{\frac {\sqrt {69}}{18}}}}\approx 1,325}$ et deux nombres complexes conjugués ${\displaystyle r,{\overline {r}}}$.

L'expression de ${\displaystyle P_{n}}$ en fonction des trois suites de base ${\displaystyle (\psi ^{n}),(r^{n}),({\overline {r}}^{n})}$ s'écrit simplement sous la forme

${\displaystyle P_{n}=\psi ^{n}+r^{n}+{\overline {r}}^{n}}$.

Des relations ${\displaystyle r+{\overline {r}}=-\psi ,r{\overline {r}}=1/\psi }$, on tire ${\displaystyle r={\frac {\mathrm {e} ^{\mathrm {i} \theta }}{\sqrt {\psi }}}}$ où ${\displaystyle \theta =\arccos(-{\sqrt {\psi ^{3}}}/2)}$, d'où la formule

${\displaystyle P_{n}=\psi ^{n}+{\frac {2\cos n\theta }{\sqrt {\psi ^{n}}}}}$

Comme ${\displaystyle \psi >1}$, on en déduit que ${\displaystyle P_{n}\sim \psi ^{n}}$ et ${\displaystyle \lim {\frac {P_{n+1}}{P_{n}}}=\psi }$,

ainsi que ${\displaystyle P_{n}=\left\lfloor \psi ^{n}\right\rceil }$ où ${\displaystyle \left\lfloor x\right\rceil }$ est l'entier le plus proche de ${\displaystyle x}$, à partir de ${\displaystyle n=10}$^[1].

Propriétés

• Relation avec la suite de Padovan, notée ici ${\displaystyle (P'_{n})}$ : ${\displaystyle P_{n}=3P'_{n-5}+2P'_{n-4}}$.
• Comme pour la suite de Fibonacci, la suite de Perrin s'obtient par puissance ${\displaystyle n}$-ième de la matrice compagnon du polynôme caractéristique :

${\displaystyle {\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}^{n}{\begin{bmatrix}3\\0\\2\end{bmatrix}}={\begin{bmatrix}P_{n}\\P_{n+1}\\P_{n+2}\end{bmatrix}}}$

et

${\displaystyle P_{n}=\psi ^{n}+r^{n}+{\overline {r}}^{n}=\operatorname {Trace} \left({\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}^{n}\right)}$.

• Fonction génératrice :
  ${\displaystyle \sum _{n=0}^{\infty }P_{n}\,x^{n}={\frac {3-x^{2}}{1-x^{2}-x^{3}}}}$

• Expression à l'aide de coefficients binomiaux pour ${\displaystyle n\geqslant 1}$ :
  ${\displaystyle P_{n}=n\times \sum _{k=\lfloor (n+2)/3\rfloor }^{\lfloor n/2\rfloor }{\frac {\binom {k}{n-2k}}{k}}}$

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 ${\displaystyle 2^{n}-2}$ soit divisible par ${\displaystyle n}$ soit un "criterium" pour que ${\displaystyle n}$ soit premier (hypothèse chinoise populaire au XIX^e siècle). On sait aujourd'hui que le nombre ${\displaystyle 341=11\times 31}$ ne passe pas ce test connu aujourd'hui comme "test de primalité de Fermat"^[1].

La suite ${\displaystyle u_{n}=2^{n}-2}$ étant définie par récurrence par ${\displaystyle u_{0}=-1,u_{1}=0,u_{n}=3u_{n-1}-2u_{n-2}}$, 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 ${\displaystyle P_{n}}$ 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^[3] : il s'agit de ${\displaystyle n}$ = 271 441 : ce nombre divise ${\displaystyle P_{271\,441}}$ mais 271 441 = 521². Le nombre ${\displaystyle P_{271441}}$ 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 ${\displaystyle p}$, la propriété ${\displaystyle P_{p}\equiv 0}$ est une conséquence de la propriété :${\displaystyle \operatorname {Trace} (A^{p})\equiv \operatorname {Trace} (A)=0}$ valable pour toute matrice à coefficients entiers^[5], utilisée ici avec la matrice ${\displaystyle A={\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}}$.

Une démonstration possible, similaire à celle du petit théorème de Fermat consistant à écrire  : ${\displaystyle a^{p}=(1+1+\cdots +1)^{p}\equiv 1+1+\cdots +1=a}$, car, d'après le théorème de Lucas, ${\displaystyle {\binom {p}{k}}\equiv 0}$ pour ${\displaystyle 1\leqslant k\leqslant p-1}$, est la suivante.

On va démontrer que ${\displaystyle P_{p}=\psi ^{p}+r^{p}+{\overline {r}}^{p}\equiv (\psi +r+{\overline {r}})^{p}}$, ce qui prouvera ${\displaystyle P_{p}\equiv 0}$, car ${\displaystyle \psi +r+{\overline {r}}=0}$.

D'après la formule du trinôme, ${\displaystyle (\psi +r+{\overline {r}})^{p}=\sum _{i+j+k=p}{\binom {p}{i,j,k}}\psi ^{i}r^{j}{\overline {r}}^{k}}$, et l'on a ${\displaystyle {\binom {p}{i,j,k}}={\frac {p!}{i!j!k!}}\equiv 0}$ pour ${\displaystyle i,j,k\leqslant p-1}$.

Les nombres ${\displaystyle \psi ,r,{\overline {r}}}$ n'étant pas entiers, on va utiliser les relations coefficients racines :

${\displaystyle {\begin{alignedat}{3}\sigma _{1}&=\psi +r+\gamma &&=0\\\sigma _{2}&=\psi r+r{\overline {r}}+{\overline {r}}\psi &&=-1\\\sigma _{3}&=\psi r{\overline {r}}&&=1.\end{alignedat}}}$

On peut alors écrire :

${\displaystyle (\psi +r+{\overline {r}})^{n}-(\psi ^{n}+r^{n}+{\overline {r}}^{n})=\sum _{i\leqslant j\leqslant k\leqslant p-1 \atop i+j+k=p}{\binom {p}{i,j,k}}\sum _{\pi (i,j,k)}\psi ^{i}r^{j}{\overline {r}}^{k}.}$

La dernière somme s'entendant pour toutes les permutations de ${\displaystyle (i,j,k)}$, elle est symétrique et s'exprime comme fonction polynomiale avec des coefficients entiers de ${\displaystyle \sigma _{1},\sigma _{2},\sigma _{3}}$ 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 ${\displaystyle n=6}$, 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 ${\displaystyle n\geqslant 2}$ est égal au nombre de Perrin ${\displaystyle P_{n}}$^[6].

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

Notes et références

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, 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, lire en ligne)

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)

v · m Nombres premiers
Donnés par une formule	combinatoire factoriel (n!±1) primoriel (pn#±1) Euclide (pn#+1) polynomiale Pythagore (4n + 1) cubain (x3 − y3)/(x − y) quatrain (x4 + y4) exponentielle Fermat (22n + 1) Mersenne (2p – 1) Double de Mersenne (22p–1 –1) Pierpont (2u3v + 1) Carol ((2n – 1)2 – 2) Kynea ((2n + 1)2 – 2) Thebit (3·2n – 1) Wagstaff ((2p + 1)/3) Proth (k2n + 1) Cullen (n2n + 1) Woodall (n2n – 1) Mills (⌊A3n⌋)
Appartenant à une suite	Fibonacci Lucas Motzkin Bell Pell Perrin Newman-Shanks-Williams
Ayant une propriété remarquable	bon chanceux fortuné Higgs illégal Pillai Ramanujan régulier Stern super supersingulier Wall-Sun-Sun Wieferich Paire de Wieferich Wilson Wolstenholme
Ayant une propriété dépendant de la base	diédral palindrome Reimerp répunit (10n − 1)/9 permutable circulaire délicat tronquable minimal long unique Smarandache-Wellin partie entière de puissances de constante troncature de constante
Propriétés mettant en jeu plusieurs nombres	singleton Chen {p ; p+2 premier ou semi-premier} équilibré (faible, fort) {pn ; pn = (<, >) (pn–1 + pn+1)/2} Sophie Germain {p ; 2p + 1 premier} sûr {p ; (p – 1)/2 premier} n-uplet jumeaux (p, p + 2) cousins (p, p + 4) sexy (p, p + 6) triplet (p, p + 2 ou p + 4, p + 6) quadruplet (p, p + 2, p + 6, p + 8) quintuplet (p – 4, p, p + 2, p + 6, p + 8) ou (p, p + 2, p + 6, p + 8, p + 12) sextuplet (p – 4, p, p + 2, p + 6, p + 8, p + 12) suite progression arithmétique (p + an) chaîne de Cunningham (p, 2p ± 1, etc.)
Classement par taille	titanesque (1 000+ chiffres) gigantesque (10 000+) méga (1 000 000+) record
Généralisations (entier quadratique)	Eisenstein Gauss
Nombre composé	pseudo-premier presque premier semi-premier interpremier
Nombre connexe	probable (NPP)
Test de primalité	Crible d'Ératosthène Test de Fermat Test de Lucas-Lehmer Test de Lucas-Lehmer pour les nombres de Mersenne Test de Pépin Test de Miller-Rabbin Test de Solovay-Strassen Test AKS
Conjectures et théorèmes de théorie des nombres	Conjecture d'Agoh-Giuga Conjecture d'Artin Conjecture de Bateman-Horn Conjecture de Bouniakovski Conjecture de Brocard Conjecture de Cramér Conjecture de Dickson Conjecture d'Elliott-Halberstam Conjecture de Firoozbakht Conjecture de Goldbach forte faible Conjecture de Grimm Conjecture de Hardy-Littlewood première seconde Conjecture de Legendre Conjecture de Lemoine Conjecture des nombres premiers de Waring Conjecture d'Oppermann Conjecture de Polignac Conjecture de Redmond-Sun Fonction de compte des nombres premiers Formules pour les nombres premiers Hypothèse H de Schinzel Nouvelle conjecture de Mersenne Théorème de Green-Tao Théorème des nombres premiers Théorème de la progression arithmétique Théorème de Rosser Théorème de Vinogradov
Constantes liées aux nombres premiers	Constante de Brun Constante de Legendre Constante de Mills Constante des nombres premiers Constante de Copeland-Erdős
Prime Pages Liste de nombres premiers Liste de suites de nombres premiers

• Portail de l'analyse