Suite de Sylvester
![](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Sylvester-square.svg/220px-Sylvester-square.svg.png)
Enthéorie des nombres,lasuite de Sylvesterest unesuited'entierstelle que chaque terme est le produit de tous les termes précédents augmenté de 1, en partant d'un terme initial égal à 2. Les premiers termes de la suite sont:
- 2;3;7;43;1 807; 3 263 443; 10 650 056 950 807; 113 423 713 055 421 844 361 000 443 (Voir la suiteA000058de l'OEIS).
En hommage à la démonstration par Euclide de l'infinitude desnombres premiers,les termes de cette suite sont aussi parfois appelés "nombres d'Euclide"[1].
La suite de Sylvester doit son nom àJames Joseph Sylvesterqui, le premier, étudia ses propriétés dans les années 1880. Ses termes présentent unecroissance exponentielle double.La série formée de la somme des inverses de cette suite converge vers 1, plus vite que toute autre série somme infinie d'inverses d'entiers convergeant vers 1.
La relation de récurrence qui définit les termes de la suite permet defactoriserceux-ci plus facilement que toute autre série de croissance comparable, mais, du fait de la croissance rapide de la série, la décomposition en nombres premiers n'est connue que pour quelques termes. Des valeurs extraites de cette suite ont été utilisées pour construire des représentations de 1 sous forme dedéveloppement en fractions égyptiennes,et intervient dans l'étude desvariétés d'Einsteinsasakiennes(en).
Définitions
[modifier|modifier le code]La suite de Sylvester est définie parrécurrenceforte:
On vérifie alors que,si bien qu'on peut également la définir par récurrence simple:
On en déduit aussi unedéfinition par récurrencedouble:
On obtient une suite strictement croissante d'entiers, donc de limite infinie.
Série des inverses et lien avec les fractions égyptiennes
[modifier|modifier le code]Comme,la série de terme généralest convergente d'après lecritère de D'Alembert.
Un résultat remarquable est que la somme de cette série est égale à 1.
En effet, il résulte de la relation de récurrence [1] que:
- ;
La somme des termes deàse réduit alors, partéléscopage,à:
Puisque la suitetend vers l'infini,tend bien vers 1.
On peut donc écrire:
ce qui donne une représentation de 1 sous forme de somme infinie defractions égyptiennes.
La même formule écrite sous la formefournit un développement de12en somme infinie de fractions égyptiennes de dénominateurs impairs.
De plus, la formule [2] écrite sous la forme:donne une représentation de 1 sous forme de somme de fractions égyptiennes de longueur quelconque (tronquer la somme infinie après un nombre arbitraire de termes et soustraire 1 du dénominateur de la dernière fraction); par exemple:
La somme despremiers termes de la suiteconstitue la meilleure approximation possible par défaut de 1 à l'aide defractions égyptiennes[2].Par exemple, la somme des quatre premiers termes de la série vaut 1805/1806 et par conséquent, pour représenter tout nombre dans l'intervalle ouvert ]1805/1806, 1[, une somme de fractions égyptiennes doit avoir au moins cinq termes. Pour cette raison, toute série d'inverses d'entiers convergeant vers 1 converge moins vite que la série des inverses de la suite de Sylvester.
On peut interpréter la suite de Sylvester comme le résultat de l'algorithme gloutonpour la décomposition du nombre 1 en somme de fractions égyptiennes, algorithme qui, à chaque étape, choisit la plus grande fraction égyptienne dont la somme avec les précédentes est strictement inférieure à 1.
Plus précisément si on pose,on obtient de nouveau la suite de Sylvester.
Étude asymptotique
[modifier|modifier le code]Comme,la suite de Sylvester présente une croissancedoublement exponentielle.
La suitetend en décroissant vers un nombreE= 1,264084735305...appelé constante de Vardi (suiteA076393de l'OEIS)[1]et on montre que non seulementmais qu'on peut calculer exactement les termes de la suite de Sylvester par la formule:
oùdésigne l'entier le plus prochede.
La croissance doublement exponentielle de la suite de Sylvester est comparable à celle de la suite desnombres de Fermat.Ceux-ci sont habituellement définis par l'expression en double exponentielle:,mais ils sont aussi définis par une récurrence très voisine de celle définissant la suite de Sylvester:
- ,alors que.
Divisibilité et factorisations
[modifier|modifier le code]Si,il résulte de la définition que.Par conséquent, deux termes quelconques de la suite de Sylvester sontpremiers entre eux.La suite peut donc servir de preuve à l'assertion "il existe une infinité de nombres premiers", puisqu'un nombre premier donné ne peut diviser qu'un terme de la suite au plus.
Plusieurs travaux ont été consacrés à la factorisation des termes de la suite de Sylvester en nombres premiers, mais il demeure beaucoup d'incertitudes à ce sujet. Par exemple, on ne sait pas si tous les termes de la suite sontsans facteurs carrés,bien que tous les termes connus le soient.
CommeVardi (1991)l'indique, il est facile de déterminer de quel terme de la suite de Sylvester (s'il existe) un nombre premierdonné est diviseur: il suffit de calculer les termes de la suite moduloà l'aide de la définition par récurrence (en répétant "remplacerpar") jusqu'à trouver un terme nul. Et si l'on obtient un terme non nul qui avait déjà été trouvé, on est assuré quene divise aucun terme de la suite. À l'aide de cette technique, il a obtenu qu'exactement 1166 des trois premiers millions de nombres premiers sont des diviseurs des nombres de Sylvester[3]et qu'aucun d'entre eux n'était élevé au carré.
Un résultat deJones (2006)conclut que la densité dans l'ensemble des nombres premiers des diviseurs premiers des termes de la suite de Sylvester est nulle.
D'autre part Odoni[4]a montré que tous les diviseurs premiers des termes de la suite de Sylvester (excepté 2 et 3) sont de la forme 6k+1.
La table ci-après présente la factorisation des termes de la suite de Sylvester (à l'exception des quatre premiers termes qui sont tous des nombres premiers)[5]:
(la notation Pn représente un nombre dechiffres dont on sait qu'il est premier, et Cn un nombre dechiffres dont on sait qu'il est composé, mais dont la décomposition est inconnue)
n | Facteurs desn |
---|---|
4 | 13 × 139 |
5 | 3263443, premier |
6 | 547 × 607 × 1033 × 31051 |
7 | 29881 × 67003 × 9 119 521 × 6 212 157 481 |
8 | 5 295 435 634 831 × 31 401 519 357 481 261 × 77 366 930 214 021 991 992 277 |
9 | 181 × 1987 × 112 374 829 138 729 × 114 152 531 605 972 711 × P68 |
10 | 2287 × 2 271 427 × 21 430 986 826 194 127 130 578 627 950 810 640 891 005 487 × P156 |
11 | 73 × C416 |
12 | 2 589 377 038 614 498 251 653 × 2 872 413 602 289 671 035 947 763 837 × C785 |
13 | 52387 × 5 020 387 × 5 783 021 473 × 401 472 621 488 821 859 737 × 287 001 545 675 964 617 409 598 279 × C1600 |
14 | 13999 × 74203 × 9 638 659 × 57 218 683 × 10 861 631 274 478 494 529 × C3293 |
15 | 17881 × 97 822 786 011 310 111 × 54 062 008 753 544 850 522 999 875 710 411 × C6618 |
16 | 128551 × C13335 |
17 | 635263 × 1 286 773 × 21 269 959 × C26661 |
18 | 50 201 023 123 × 139 263 586 549 × 60 466 397 701 555 612 333 765 567 × C53313 |
19 | C106721 |
20 | 352867 × 6 210 298 470 888 313 × C213419 |
21 | 387 347 773 × 1 620 516 511 × C426863 |
22 | 91 798 039 513 × C853750 |
La liste croissante des nombres premiers qui divisent un terme de la suite de Sylvester est répertoriéeA007996dans l'OEIS.
Généralisation: développement en série de Sylvester d'un réel quelconque
[modifier|modifier le code]On peut généraliser l'algorithme gloutonde décomposition en somme infinie defractions égyptiennesà un réel strictement positifautre que 1: cet algorithme choisit, à chaque étape, la plus grande fraction égyptienne dont la somme avec les précédentes est strictement inférieure à.
On pose donc,ou, de façon plus pratique:
- puis pour tout entier naturel:.
Ledéveloppement en série deSylvesterdes'écrit alors:
- que l'on notera.
La suite d'entiers naturels non nulsest alors définie de façon unique par le fait quepour toutet le réelest rationnel si et seulement sià partir d'un certain rang.
Le développement du nombre 1 correspond bien sûr à la suite de Sylvester vue ci-dessus:.
Exemples irrationnels:
Si au lieu de prendre la plus grande fraction égyptienne dont la somme avec les précédentes eststrictementinférieure à,on prend celle qui est inférieureou égaleà,l'algorithme est identique siest irrationnel, mais il s'arrête siest rationnel et on obtient ledéveloppement égyptien glouton finide.
Par exemple,.
Le développement en série de Sylvester a des liens aveccelui de Engel[6].
Unicité des séries à croissance rapide ayant une limite rationnelle
[modifier|modifier le code]Sylvester observa lui-même que la suite qui porte maintenant son nom semblait posséder la propriété unique d'avoir une croissance extrêmement rapide, tandis que la série somme de ses inverses convergeait vers un rationnel.
Plus précisément, il résulte des travaux deBadea (1993)que, si une suite d'entierscroît suffisamment pour qu'à partir d'un certain rang:
et si la série:converge vers unrationnel,alors, pour toutau-delà d'une certaine valeur, la suite peut être définie par la même relation de récurrence que la suite de Sylvester:
En 1980,Erdősconjecturaque pour les résultats de ce type, l'inégalité conditionnant la croissance de la suite pouvait être remplacée par la condition plus faible:
- .
Applications
[modifier|modifier le code]Boyer et al. (2005)utilisent les propriétés de la suite de Sylvester pour spécifier le grand nombre devariétés d'Einsteinsasakiennes(en)possédant latopologie différentielledesphèresde dimension impaire ou d'autressphères exotiques.Ils démontrent que le nombre demétriques riemanniennesdes variétés d'Einstein sasakiennes sur unesphère topologiquede dimensionest au moins proportionnelle àet croît donc selon une double exponentielle de.
SelonGalambos et Woeginger (1995),Brown (1979)etLiang (1980)ont utilisé la suite de Sylvester pour construire un algorithme séquentiel minimisant leproblème de bin packing.Seiden et Woeginger (2005)ont aussi utilisé cette suite pour élaborer un algorithme minimisant leproblème de bin packingà deux dimensions[7].
Leproblème de Známconsiste à trouver un ensemble de nombres tel que chacun divise le produit de tous les autres plus 1, sans être égal à cette valeur. Si ce n'était cette dernière condition, les ensembles formés des premiers termes de la suite de Sylvester seraient des solutions à ce problème. Avec cette condition, les solutions constituent une suite dont la définition est similaire à celle de la suite de Sylvester. Les solutions du problème de Znám ont des applications dans la classification des singularités des surfacesBrenton et Hill (1988)et dans la théorie desautomates finis non déterministes(Domaratzkiet al.2005).
Curtiss (1922)présente une approximation de 1 par la somme defractions unitairescomme approximation inférieure du nombre de diviseurs de toutnombre parfaitetMiller (1919)utilise la même propriété pour minimiser la taille de certains groupes.
Notes et références
[modifier|modifier le code]- Graham, Knuth et Patashnik (1989)
- Proposition généralement attribuée àCurtiss (1922),maisMiller (1919)a fait la même observation dans un article antérieur. Voir aussiRosenman (1933),Salzer (1947)etSoundararajan (2005).
- Andersen, lui, a trouvé 1167 diviseurs premiers dans ces trois premiers millions.
- (en)R. W. K. ODONI,On the prime divisors of the sequence w(n+1) =1+w(1)⋯w(n),Londres, J. Lond. Math. Soc., II. Ser.,(lire en ligne),p.1–11
- Les facteurs premierspde la suite de Sylvestersnavecp< 5×107etn≤ 200 sont listés par Vardi. Ken Takusagawa liste lesfactorisations jusqu'às9et lafactorisation des10.Les autres factorisations sont issues deListe des factorisations de la suite de Sylvestertenue par Jens Kruse Andersen (version du 28/06/2014).
- (en)Jun Wu, «How many points have the same Engel and Sylvester expansions?»,Journal of Number Theory Volume 103, Issue 1,,p.16-26(lire en ligne)
- Dans leur article,Seiden et Woeginger (2005)utilisent le nom de "Suite de Salzer" au lieu de celui de "Suite de Sylvester", d'après l'article deSalzer (1947)sur les problèmes de minimisation.
Voir aussi
[modifier|modifier le code]Bibliographie
[modifier|modifier le code]- (en)CatalinBadea,«A theorem on irrationality of infinite series and applications»,Acta Arithmetica,vol.63,,p.313-323
- (en)Catalin Badea, «On some criteria for irrationality for series of positive rationals: a survey»,
- (en)Charles P.Boyer,KrzysztofGalickietJános Kollár,«Einstein metrics on spheres»,Ann. of Math.,vol.162,no1,,p.557-580(DOI10.4007/annals.2005.162.557,lire en ligne)
- (en)LawrenceBrentonet RichardHill,«On the Diophantine equation 1=Σ1/ni+ 1/Πniand a class of homologically trivial complex surface singularities»,Pacific J. Math.,vol.133,no1,,p.41-67(lire en ligne)
- (en)D. J.Brown,A lower bound for on-line one-dimensional bin packing algorithms; Version = Tech. Rep. R-864,Coordinated Science Lab.,Univ. Illinois, Urbana-Champaign,
- (en)D. R.Curtiss,«On Kellogg's diophantine problem»,Amer. Math. Monthly,vol.29,,p.380-387(DOI10.2307/2299023,JSTOR2299023)
- (en)MichaelDomaratzki,KeithEllul,Jeffrey Shallitet Ming-WeiWang,«Non-uniqueness and radius of cyclic unary NFAs»,International Journal of Foundations of Computer Science,vol.16,no5,,p.883-896(DOI10.1142/S0129054105003352,lire en ligne)
- (en)PaulErdősetRonald Graham,Old and New Problems and Results in Combinatorial Number Theory,Univ. de Genève,coll.« Monographies deL'Enseignement mathématique» (no28),
- (en)GáborGalambosetGerhard J.Woeginger,«On-line bin packing — A restricted survey»,Mathematical Methods of Operations Research,vol.42,no1,,p.25(DOI10.1007/BF01415672)
- (en)Solomon Golomb,«On certain nonlinear recurring sequences»,Amer. Math. Monthly,vol.70,no4,,p.403-405(DOI10.2307/2311857,JSTOR2311857)
- (en)Ronald Graham,Donald KnuthetOren Patashnik,Concrete Mathematics,Addison-Wesley,(ISBN0-201-55802-5),Exercise4.37
- (en)Rafe Jones, «The density of prime divisors in the arithmetic dynamics of quadratic polynomials»,(arXivmath/0612415v1)
- (en)Frank M. Liang, «A lower bound for on-line bin packing»,Information Processing Letters,vol.10,no2,,p.76-79(DOI10.1016/S0020-0190(80)90077-0)
- (en)G. A. Miller(en),«Groups possessing a small number of sets of conjugate operators»,Trans. Amer. Math. Soc.,vol.20,no3,,p.260-270(DOI10.2307/1988867,JSTOR1988867)
- (en)Martin Rosenman, «Problem 3536»,Amer. Math. Monthly,vol.40,no3,,p.180(JSTOR2301036)
- (en)H. E. Salzer,«The approximation of numbers as sums of reciprocals»,Amer. Math. Monthly,vol.54,no3,,p.135-142(DOI10.2307/2305906,JSTOR2305906)
- (en)Steven S.SeidenetGerhard J.Woeginger,«The two-dimensional cutting stock problem revisited»,Math. Prog.,vol.102,no3,,p.519-530(DOI10.1007/s10107-004-0548-1)
- (en)K. Soundararajan,«Approximating 1 from below usingnEgyptian fractions»,(arXivmath/0502247v1)
- (en)J. J. Sylvester,«On a point in the theory of vulgar fractions»,Amer. J. Math.,vol.3,no4,,p.332-335(DOI10.2307/2369261,JSTOR2369261)
- (en)IlanVardi,Computational Recreations in Mathematica,Redwood City (Calif.),Addison-Wesley,,286p.(ISBN0-201-52989-0),p.82-89
Articles connexes
[modifier|modifier le code]Liens externes
[modifier|modifier le code]- (en)Irrationality of Quadratic Sums,MathPagesde K. S. Brown.
- (en)Eric W. Weisstein,«Sylvester's Sequence», surMathWorld