Suite de Sylvester

Suite de Sylvester
Démonstration graphique de la convergence vers 1 de la somme 1/2 + 1/3 + 1/7 + 1/43 +... Chaque rang de n carrés de côté 1/n a une aire totale de 1/n ; l'ensemble des rangs recouvre exactement un carré plus grand, d'aire 1. [Les carrés de côté 1/1807 ou moins sont trop petits pour être dessinés sur le graphique.)

En théorie des nombres, la suite de Sylvester est une suite d'entiers telle que chaque terme de la suite est le produit de tous les termes précédents plus 1. 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 suite A000058 de l’OEIS). Usuellement, on pose : s0 = 2.

La suite de Sylvester doit son nom à James Joseph Sylvester qui, le premier, étudia ses propriétés dans les années 1880. Ses termes croissent selon une fonction exponentielle double. La série formée de la somme des inverses de la suite de Sylvester 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 de factoriser ceux-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 ses premiers termes. Des valeurs extraites de cette suite ont été utilisées pour construire des représentations de 1 sous forme de fraction égyptienne, des variétés d'Einstein (en) sasakiennes (en), et l'élaboration d'algorithmes résolvant des problèmes difficiles.

Sommaire

Définitions

La suite de Sylvester peut être définie formellement par la relation :

s_n = 1 + \prod_{i = 0}^{n - 1} s_i

On peut également définir la série par la relation de récurrence [1] :

 \displaystyle s_i = s_{i-1}*(s_{i-1}-1)+1

Les deux définitions étant prises avec s0 = 2.

Ces deux définition sont équivalentes, comme le montre facilement un raisonnement par récurrence.

Lien avec les fractions égyptiennes

La somme des inverses des termes successifs de la suite de Sylvester génère la série infinie [2] :

\sum_{i=0}^{\infty} \frac1{s_i} = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{1807} + \cdots

Cette série infinie converge vers 1. En effet, il résulte de la définition par réccurence [1] que :

\frac{1}{s_i-1}-\frac{1}{s_{i+1}-1}=\frac{1}{s_i}

La série partielle constituée de la somme des termes de 1/s0 à 1/sj se réduit alors à :

\sum_{i=0}^{j-1} \frac{1}{s_i} = \sum_{i=0}^{j-1} \left( \frac{1}{s_i-1}-\frac{1}{s_{i+1}-1} \right) = \frac{1}{s_0-1} - \frac{1}{s_j-1} = 1 - \frac{1}{s_j-1}

Puisque, lorsque j tend vers l'infini, sj tend également vers l'infini, la série [2] tend vers 1.

Ainsi, la série [2] est une représentation de 1 sous forme de fraction égyptienne infinie :

1 = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{1807} + \cdots

On peut trouver une représentation de 1 sous forme de fraction égyptienne de longueur quelconque en tronquant la série [2] après un nombre arbitraire de termes et en soutrayant 1 du dénominateur de la dernière fraction :

1 = \tfrac12 + \tfrac13 + \tfrac16, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{42}, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{43} + \tfrac1{1806},\quad \dots

La somme des k premiers termes de la série [2] constitue la plus proche approximation possible par défaut de 1 à l'aide d'une fraction égyptienne[1]. Par exemple, les quatre premiers termes de la série [2] valent 1805/1806 et par conséquent, pour représenter tout nombre dans l'ouvert (1805/1806 ; 1), une fraction égyptienne doit avoir au moins cinq termes.

On peut interpréter la suite de Sylvester comme le résultat d'un algorithme glouton pour les fractions égyptiennes qui, à chaque étape, choisit le plus petit dénominateur produisant une série partielle de somme inférieure à 1. Réciproquement, on peut considérer les termes après s0 comme le développement en fraction égyptienne à dénominateurs impairs de 1/2.

Valeurs approchées, valeurs asymptotiques

Les termes de la suite de Sylverster croissent comme une exponentielle double de n. On montre, en particulier, que :

s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor

où \lfloor x \rfloor est l'arrondi inférieur (arrondi par troncation) de la valeur x et où E ≈ 1.264084735305 est la constante de Vardi (suite A076393 de l’OEIS)[2]. Cette formule conduit à l'algorithme suivant pour le calcul de sn :

s0 est l'entier le plus proche inférieur à E2 ; s1 est l'entier le plus proche inférieur à E4 ; s2 est l'entier le plus proche inférieur à E8 ; et pour sn, prendre E2, puis calculer la puissance nième du résultat et l'arrondir à l'entier inférieur le plus proche. Cet algorithme ne serait efficace que s'il existait une autre méthode pour calculer la constante de Vardi que de calculer explicitement les termes de la série de Sylvester et d'en prendre les racines carrées successives...

La croissance en exponentielle double de la suite de Sylvester est comparable à la croissance de la suite des nombres de Fermat Fn. Ceux-ci sont habituellement définis par l'expression en double exponentielle : 2^{2^n}+1, mais ils sont aussi définis par un produit très voisin de la définition de la suite de Sylvester :

F_n = 2 + \prod_{i = 0}^{n - 1} F_i

Unicité des séries à croissance rapide ayant une limite rationnelle

Sylvester observa lui-même que la suite qui porte son nom semblait posséder la propriété unique d'avoir une croissance extrêmement rapide, alors que la série somme de ses inverses convergeait vers un rationnel.

Plus précisément, il résulte des travaux de Badea (1993) que, si une suite d'entiers an croît suffisant pour que

a_n\ge a_{n-1}^2-a_{n-1}+1

et si la série

A=\sum\frac1{a_i}

converge vers un rationnel A, alors, pour tout n au-delà d'une certaine valeur, la suite peut être définie par la même relation de récurrence

a_n= a_{n-1}^2-a_{n-1}+1

que la suite de Sylvester.

Erdős (1980) conjectura (en) que 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 :

\lim_{n\rightarrow\infty} \frac{a_n}{a_{n-1}^2}=1

Divisibilité et factorisations

Si i < j, il résulte de la définition que sj ≡ 1 (mod si). Par conséquent, deux termes quelconques de la suite de Sylvester sont premiers entre eux. La suite peut donc servir de preuve à l'assertion "il y a 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 sont sans facteurs carrés, bien que tous les termes connus le soient.

Comme Vardi (1991) l'indique, il est facile de déterminer quel terme (s'il existe) de la suite de Sylvester divise un nombre premier p donné : il suffit de calculer les termes de la suite (modulo p) à l'aide de la définition par récurrence jusqu'à trouver un terme congruent à 0 (modulo p) ou un module répété. À l'aide de cette technique, il a pu trouver que 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 de Jones (2006) conclut que la densité des diviseurs premiers de la suite de Sylvester a une densité de 0 dans l'ensemble des nombres premiers.

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)[4] :

n Facteurs de sn
4 13 × 139
5 3263443, premier
6 547 × 607 × 1033 × 31051
7 29881 × 67003 × 9119521 × 6212157481
8 5295435634831 × 31401519357481261 × 77366930214021991992277
9 181 × 1987 × 112374829138729 × 114152531605972711 × P68
10 2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
11 73 × C416
12 2589377038614498251653 × 2872413602289671035947763837 × C785
13 52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14 13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15 17881 × 97822786011310111 × C6649
16 128551 × C13335
17 635263 × 1286773 × 21269959 × C26661
18 50201023123 × 139263586549 × C53339
19 C106721
20 352867 × 6210298470888313 × C213419
21 387347773 × 1620516511 × C426863
22 91798039513 × C853750

Pn représente un nombre de n chiffres dont on sait qu'il est premier, et Cn un nombre de n chiffres dont on sait qu'il est composé, mais dont la décomposition est inconnue.

Applications

Boyer et al. (2005) utilisent les propriétés de la suite de Sylvester pour spécifier le grand nombre de variétés d'Einstein (en) sasakiennes (en) possédant la topologie différentielle de sphères de dimension impaire ou d'autres sphères exotiques. Ils démontrent que le nombre de métriques riemanniennes des variétés d'Einstein sasakiennes sur une sphère topologique de dimension 2n − 1 est au moins proportionnelle à sn et croît donc selon une double exponentielle de n.

Selon Galambos et Woeginger (1995), Brown (1979) et Liang (1980) ont utilisé la suite de Sylvester pour construire un algorithme séquentiel minimisant le problème de bin packing. Seiden et Woeginger (2005) ont aussi utilisé cette suite pour élaborer un algorithme minimisant le problème de bin packing à deux dimensions[5].

Le problème de Znám (en) consiste à 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, la suite de Sylvester serait une solution du problème. Avec cette condition, les solutions constituent une série 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 surfaces Brenton et Hill (1988) et dans la théorie des automates finis non déterministes (Domaratzki et al. 2005).

Curtiss (1922) présente une approximation de 1 par la somme de k fractions unitaires comme approximation inférieure du nombre de diviseurs de tout nombre parfait et Miller (1919) utilise la même propriété pour minimiser la taille de certains groupes.

Annexes

Bibliographie

  • (en) Catalin Badea, « A theorem on irrationality of infinite series and applications », dans Acta Arithmetica (en), vol. 63, 1993, p. 313–323 
  • (en) Catalin Badea, « On some criteria for irrationality for series of positive rationals: a survey », 1995
  • (en) Charles P. Boyer, Krzysztof Galicki et János Kollár (en), « Einstein metrics on spheres », dans Ann. of Math., vol. 162, no 1, 2005, p. 557–580 [texte intégral, lien DOI] 
  • (en) Lawrence Brenton et Richard Hill, « On the Diophantine equation 1=Σ1/ni + 1/Πni and a class of homologically trivial complex surface singularities », dans Pacific J. Math. (en), vol. 133, no 1, 1988, p. 41–67 [texte intégral] 
  • (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, 1979 
  • (en) D. R. Curtiss, « On Kellogg's diophantine problem », dans Amer. Math. Monthly, vol. 29, 1922, p. 380–387 [texte intégral, lien DOI] 
  • (en) Michael Domaratzki, Keith Ellul, Jeffrey Shallit et Ming-Wei Wang, « Non-uniqueness and radius of cyclic unary NFAs », dans International Journal of Foundations of Computer Science, vol. 16, no 5, 2005, p. 883–896 [texte intégral, lien DOI] 
  • (en) Paul Erdős et Ronald Graham, Old and new problems and results in combinatorial number theory, vol. 28, t. Monographies de L'Enseignement Mathématique, Univ. de Genève 
  • (en) Gábor Galambos et Gerhard J. Woeginger, « On-line bin packing — A restricted survey », dans Mathematical Methods of Operations Research, vol. 42, no 1, 1995, p. 25 [lien DOI] 
  • (en) Solomon Golomb, « On certain nonlinear recurring sequences », dans Amer. Math. Monthly, vol. 70, no 4, 1963, p. 403–405 [texte intégral, lien DOI] 
  • (en) Ronald Graham, Donald Knuth et Oren Patashnik (en), Concrete Mathematics (en), Addison–Wesley, 1989 (ISBN 0-201-55802-5) , Exercise 4.37
  • (en) Rafe Jones, The density of prime divisors in the arithmetic dynamics of quadratic polynomials , arXiv:math/0612415v1
  • (en) Frank M. Liang, « A lower bound for on-line bin packing », dans Information Processing Letters, vol. 10, no 2, 1980, p. 76–79 [lien DOI] 
  • (en) G. A. Miller (en), « Groups possessing a small number of sets of conjugate operators », dans Trans. Amer. Math. Soc., vol. 20, no 3, 1919, p. 260–270 [texte intégral, lien DOI] 
  • (en) Martin Rosenman, « Problem 3536 », dans Amer. Math. Monthly, vol. 40, no 3, 1933, p. 180 [texte intégral] 
  • (en) H. E. Salzer, « The approximation of numbers as sums of reciprocals », dans Amer. Math. Monthly, vol. 54, no 3, 1947, p. 135–142 [texte intégral, lien DOI] 
  • (en) Steven S. Seiden et Gerhard J. Woeginger, « The two-dimensional cutting stock problem revisited », dans Math. Prog. (en), vol. 102, no 3, 2005, p. 519–530 [lien DOI] 
  • (en) K. Soundararajan, Approximating 1 from below using n Egyptian fractions, 2005 , arXiv:math/0502247v1
  • (en) J. J. Sylvester, « On a point in the theory of vulgar fractions », dans Amer. J. Math. (en), vol. 3, no 4, 1880, p. 332–335 [texte intégral, lien DOI] 
  • (en) Ilan Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991 (ISBN 0-201-52989-0), p. 82–89 

Notes et références

  1. ↑ Proposition généralement attribuée à Curtiss (1922), mais Miller (1919) a fait la même observation dans un article antérieur. Voir aussi Rosenman (1933), Salzer (1947) et Soundararajan (2005).
  2. ↑ Graham, Knuth et Patashnik (1989) font un exercice du calcul de cette constante ; voir aussi Golomb (1963).
  3. ↑ Andersen, lui, a trouvé 1167 diviseurs premiers dans ces trois premiers millions.
  4. ↑ Les facteurs premiers p de la suite de Sylvester sn avec p < 5×107 et n ≤ 200 sont listés par Vardi. Ken Takusagawa liste les factorisations jusqu'à s9 et la factorisation de s10. Les autres factorisations sont issues de Liste des factorisations de la suite de Sylvester tenue par Jens Kruse Andersen (version du 27/01/2007).
  5. ↑ 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 de Salzer (1947) sur les problèmes de minimisation.

Voir aussi

Articles connexes

  • Constante de Cahen (en)
  • Nombre pseudoparfait primaire (en)

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite de Sylvester de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Sylvester Stadler — Surnom Vestl Naissance 30 décembre 1910 Fohnsdorf …   Wikipédia en Français

  • Sylvester Stallone — Pour les articles homonymes, voir Stallone. Sylvester Stallone …   Wikipédia en Français

  • Sylvester, Josuah — (1563 1618)    Born in Kent and orphaned at a young age, he was raised by an uncle and educated at a school in Southampton, Hampshire, where not being fluent in French ensured wearing the dunce s cap. In 1606 Prince Henry made him a groom of his… …   British and Irish poets

  • James Joseph Sylvester — James Joseph Sylvester, mathématicien et géomètre anglais, est né à Londres le 3 septembre 1814 et est décédé à Mayfair le 13 mars 1897. Il a commencé à enseigner les …   Wikipédia en Français

  • James Sylvester — James Joseph Sylvester James Joseph Sylvester James Joseph Sylvester, mathématicien et géomètre anglais, est né à Londres le 3 septembre 1814 et est décédé à Mayfair le 13 mars 1897. Il a enseigné les mathématiques à partir de 18 …   Wikipédia en Français

  • William Sylvester — Données clés Nom de naissance William Sylvester Naissance 31 janvier 1922 Oakland (Californie) Nationalité Am …   Wikipédia en Français

  • Richard H. Sylvester — For the Iowa journalist, see Richard H. Sylvester (writer). Richard H. Sylvester Sylvester circa 1913 Born 1860 Iowa, USA Died …   Wikipedia

  • Friedrich Christian Albert Leopold Anno Sylvester Macarius Prinz von Sachsen Herzog zu Sachsen — (* 31. Dezember 1893 in Dresden; † 9. August 1968 in Samedan, Schweiz) war der zweitälteste Sohn König Friedrich August III. von Sachsen, des letzten Königs von Sachsen und seiner Frau Luise von Toskana und war seit dem Tod seines Vaters 1932… …   Deutsch Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”