Mostra la font per a Seqüència de Sylvester

[[Fitxer:Sylvester-square.svg|miniatura|Demostració gràfica de la convergència a la unitat de la suma 1/2 + 1/3 + 1/7 + 1/43 + ... Cada filera de ''k'' quadrats de costat 1/''k'' té àrea total 1/''k'', i tots els quadrats junts cobreint exactament un quadrat més gros que té àrea u. Els quadrats de costat 1/1807 o més petit són massa petits per ser vistos a la figura, i no hi són .]]
En [[teoria dels nombres]], la '''seqüència de Sylvester''' és una [[successió (matemàtiques)|seqüència]] d'[[Nombre enter|enters]] en què cada membre de la seqüència és el producte dels membres anteriors més u. Els primers termes de la seqüència són:
[[Dos|2]], [[Tres|3]], [[Set (nombre)|7]], [[Quaranta-tres|43]], 1807, 3263443, 10650056950807, 113423713055421844361000443 {{OEIS|id=A000058}}.

La seqüència de Sylvester pren el nom de [[James Joseph Sylvester]], qui la investigà per primera vegada el 1880. Els seus valors creixen [[funció doblement exponencial|doblement exponencialment]], i la suma dels seus [[recíproc]]s forma una [[Sèrie matemàtica|sèrie]] de [[fracció unitària|fraccions unitàries]] que convergeix a la unitat més aviat que qualsevol altra sèrie de fraccions unitàries amb la mateixa suma. La [[recurrència]] que la defineix permet una [[Factorització dels enters|Factorització]] més senzilla que la d'altres nombres qualssevol de la mateixa mida, però, a causa del ràpid creixement de la seqüència, només es coneixen les factoritzacions completes en nombres primeres d'alguns dels seus termes. Els valors derivats d'aquesta seqüència s'han fet servir per construir representacions en [[Fracció egipciana|fraccions egipcianes]] de suma 1, així com en [[varietat saskiana|varietats saskianes]] i les [[Varietat d'Einstein|d'Einstein]].

== Definicions formals ==
Formalment, la seqüència de Sylvester es pot definir per la fórmula

:<math>s_n = 1 + \prod_{i = 0}^{n - 1} s_i.</math>

El [[producte buit|producte d'un conjunt buit]] és 1, car ''s''<sub>0</sub> = 2.

Altrament, es pot definir la seqüència per la [[recurrència]]
:<math>\displaystyle s_i = s_{i-1}(s_{i-1}-1)+1,</math> amb ''s''<sub>0</sub> = 2.
Es pot demostrar per inducció que totes dues definicions són equivalents.

== Relació amb les fraccions egipcianes ==
Les [[fracció unitària|fraccions unitàries]] formades pels [[recíproc]]s dels valors de la seqüència de Sylvester generen una [[sèrie infinita]]:

:<math>\sum_{i=0}^{\infty} \frac1{s_i} = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{1807} + \cdots</math>

Les sumes parcials d'aquesta sèrie tenen una forma simple,

:<math>\sum_{i=0}^{j-1} \frac1{s_i} = \frac{s_j-2}{s_j-1},</math>
com es pot demostrar per inducció. Aquesta identitat és certa per a ''j'' 0, ja que tots dos costats són zero. Per a ''j'' més grans, estendre el costat esquerre de la identitat fent servir la hipòtesi d'inducció dona
:<math>\sum_{i=0}^{j-1} \frac1{s_i} = \frac1{s_{j-1}}+\sum_{i=0}^{j-2} \frac1{s_i} = \frac1{s_{j-1}}+\frac{s_{j-1}-2}{s_{j-1}-1} = \frac{s_{j-1}(s_{j-1}-1)-1}{s_{j-1}(s_{j-1}-1)} = \frac{s_j-2}{s_j-1},</math>
com es volia demostrar. Atès que aquesta seqüència de sumes parcials (''s''<sub>''j''</sub>-2)/(''s''<sub>''j''</sub>-1) convergeix a u, la sèrie global forma una representació en [[fracció egipciana]] infinita del nombre u:
:<math>1 = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{1807} + \cdots</math>
Es poden trobar representacions de la unitat en fraccions egipcianes finites, de qualsevol longitud, truncant aquesta sèrie i restant u del darrer denominador:
:<math>1 = \tfrac12 + \tfrac13 + \tfrac16, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{42}, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{43} + \tfrac1{1806},\quad \dots</math>
La suma dels primers ''k'' termes de la sèrie infinita dona l'estimació per defecte més propera possible a la unitat que qualsevol fracció egipciana de ''k'' termes.<ref>Aquesta afirmació se sol atribuir a Curtiss (1922), però Miller (1919) sembla que feu la mateixa afirmació en una publicació anterior. Vegeu també Rosenman (1933), Salzer (1947), i Soundararajan (2005).</ref> Per exemple, els primers quatre termes sumen 1805/1806, i, per tant, qualsevol fracció egipciana d'un nombre dins l'interval obert (1805/1806, 1) té almenys cinc termes.

Es pot interpretar la seqüència de Sylvester com el resultat d'un [[algorisme voraç]] per a fraccions egipcianes que en cada etapa tria el denominador més petit possible que fa la suma parcial de la sèrie més petita que 1. Altrament, els termes de la seqüència després del primer es poden interpretar com els denominadors de l'[[expansió voraç imparell]] d'1/2.

== Fórmula en forma tancada i asimptòtica ==
Els nombres de Sylvester creixen [[funció doblement exponencial|doblement exponencialment]] com a funció de ''n''. En particular, es pot demostrar que

:<math>s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor,</math>

per a un nombre ''E'' que és aproximadament 1.264.<ref>Graham, Knuth, and Patashnik (1989) ho proposen com a exercici; vegeu també Golomb (1963).</ref> Aquesta fórmula fa l'efecte de l'algorisme següent:
:s<sub>0</sub> és l'enter més proper a E²; s<sub>1</sub> és l'enter més proper a E<sup>4</sup>; s₂ és l'enter més proper a E<sup>8</sup>; per a s<sub>''n''</sub>, preneu E², elevau-lo al quadrat ''n'' vegades més, i preneu-hi l'enter més proper.
Això només seria un algorisme pràctic si hi hagués una forma millor de calcular E amb la precisió requerida que no calcular s<sub>''n''</sub> i prendre'n l'arrel quadrada repetidament.

El creixement doblement exponencial de la seqüència de Sylvester no resulta sorprenent si se'l compara a la seqüència dels [[nombre de Fermat|nombres de Fermat]] ''F''<sub>''n''</sub>; els nombres de Fermat es defineixen habitualment amb una fórmula doblement exponencial, <math>2^{2^n}+1</math>, però també es poden definir amb una fórmula de productes molt semblant a la que defineix la seqüència de Sylvester:

:<math>F_n = 2 + \prod_{i = 0}^{n - 1} F_i.</math>

== Unicitat de la sèrie de creixement ràpid amb sumes racionals ==
Com Sylvester mateix observà, la seqüència de Sylvester sembla l'única que té valors que creixin tan ràpidament, alhora que té una sèrie de recíprocs que convergeix a un [[nombre racional]].

Més precisament, es deriva de resultats de Badea (1993) que, si una seqüència d'enters <math>a_n</math> creix prou aviat que
:<math>a_n\ge a_{n-1}^2-a_{n-1}+1,</math>
i si la sèrie
:<math>A=\sum\frac1{a_i}</math>
convergeix a un nombre racional ''A'', aleshores, per a tot ''n'' després de qualque punt, aquesta seqüència ha de ser definida per la mateixa recurrència
:<math>a_n= a_{n-1}^2-a_{n-1}+1</math>
que es pot fer servir per definir la seqüència de Sylvester.

[[Paul Erdős|Erdős]] (1980) [[conjectura d'Erdős|conjecturà]] que, en els resultats d'aquesta mena, la inequalitat que limita el creixement de la seqüència es podria substituir per una condició més feble,
:<math>\lim_{n\rightarrow\infty} \frac{a_n}{a_{n-1}^2}=1.</math>
Badea (1995) recull els progressos lligats a aquesta conjectura; vegeu també Brown.

== Divisibilitat i factoritzacions ==
Si ''i'' < ''j'', se segueix de la definició que ''s''<sub>''j''</sub> ≡ 1 (mod ''s''<sub>''i''</sub>). Per tant, tot parell de nombres en la seqüència de Sylvester són [[primers entre si]]. La seqüència es pot fer servir per demostrar que hi ha infinits [[Nombre primer|nombres primers]], ja que qualsevol primer divideix, com a màxim, un nombre de la seqüència.

S'han esmerçat esforços a factoritzar dels nombres de la seqüència de Sylvester, però es desconeix molta cosa sobre llur factorització. Per exemple, es desconeix si tots els nombres en la seqüència són [[lliure de quadrats|lliures de quadrats]], tot i que tots els termes coneguts ho són.

Com Vardi (1991) descriu, és senzill de determinar quin nombre de Sylvester (si n'hi ha cap) un nombre primer donat divideix: n'hi ha prou a computar la recurrència que defineix els nombres modulo ''p'' fins que es troba un nombre congruent a zero (mod ''p'') o bé un mòdul repetit. Per mitjà d'aquesta tècnica trobà que 1166 dels tres primers milions de nombres primers són divisors dels nombres de Sylvester.<ref>(això sembla un error, ja que Andersen troba 1167 divisors primers en aquest marge)</ref> i que cap d'aquests primers no té un quadrat que divideixi un nombre de Sylvester. Un resultat general de Jones (2006) implica que el conjunt dels factors primers dels nombres de Sylvester té densitat zero dins el conjunt de tots els primers.

La taula següent mostra les factoritzacions conegudes d'aquests nombres, (llevat dels quatre primers, que són tots primers):<ref>Tots els factors primers ''p'' dels nombres de Sylvester ''s''<sub>''n''</sub> amb ''p'' &lt; 5×10<sup>7</sup> i ''n'' ≤ 200 són enumerats per Vardi. Ken Takusagawa enumera les [http://kenta.blogspot.com/2006/01/factoring-sylvesters-sequence.html factorizations fins a ''s''<sub>9</sub>] i la [http://kenta.blogspot.com/2006/04/sylvester-10th-factored.html factorització de ''s''<sub>10</sub>]. La resta de factoritzacions són d'una [http://hjem.get2net.dk/jka/math/sylvester-factors.htm llista de factoritzacions de la seqüència de Sylvester] {{Webarchive|url=https://web.archive.org/web/20070927235957/http://hjem.get2net.dk/jka/math/sylvester-factors.htm |date=2007-09-27}} que manté Jens Kruse Andersen, consultada el 2 d'octubre de 2007.</ref>

{| class=wikitable
! ''n''
! Factors de ''s''<sub>''n''</sub>
|-
|4
|13 × 139
|-
|5
|3263443, que és primer
|-
|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
|}

Com és habitual, P''n'' i C''n'' denoten nombres primers i compostos de ''n'' dígits.

== Aplicacions ==
{{Millorar traducció|data=2020}}
Boyer i cols. (2005) fan servir les propietats de la seqüència de Sylvester per definir grans nombres de [[Sasakian manifold|Sasakian]] [[Einstein manifold]]s que tenen la [[topologia diferencial]] d'[[hiperesfera|hiperesferes]] de dimensió senar o d'[[esfera exòtica|esferes exòtiques]]. Demostren que el nombre de mètriques Sasakian Einstein sobre una [[esfera topològica]] de dimensió 2''n'' − 1 is almenys proporcional a ''s''<sub>''n''</sub> i doncs té creixement doblement exponencial amb ''n''.

Com descriuen Galambos i Woeginger (1995), Brown (1979) i Liang (1980) usaren valors derivats de la seqüència de Sylvester per construir exemples de límit inferior per a algorismes de [[bin packing]] en línia. De forma semblant, Seiden i Woeginger (2005) fan servir la seqüència per fitar inferiorment el rendiment d'un ''cutting stock algorithm'' bidimensional.<ref>En el seu treball, Seiden i Woeginger es refereixen a la seqüència de Sylvester com a "seqüència de Salzer" després de l'article de Salzer (1947) sobre l'aproximació més propera.</ref>

El [[problema de Znám]] es refereix a conjunts de nombres tals que cada nombre del conjunt divideix però no és igual al producte de tots els altres nombres, més u. Sense el requeriment de la inequalitat, els valors de la seqüència de Sylvester resoldrien el problema; amb aquest requeriment, té d'altres solucions derivades de recurrències semblants a la que defineix la seqüència de Sylvester. Les solucions al problema de Znám tenen aplicacions a la classificació de singularitats de superfícies (Brenton i Hill 1988) i a la teoria dels [[autòmat finit no determinístic|autòmats finits no determinístics]] (Domaratzki i cols. 2005).

Curtiss (1922) descriu una aplicació de les aproximacions més properes a la unitat amb sumes de fraccions unitàries de ''k'' termes, en la determinació d'una fita inferior dels nombre de divisors de qualsevol [[nombre perfecte]], i Miller (1919) usa la mateixa propietat per afitar inferiorment la mida de determinats grups.

== Notes ==
{{Referències}}

== Bibliografia ==
{{refbegin|2}}
* {{ref-publicació|autor= Badea, Catalin|títol= A theorem on irrationality of infinite series and applications|any= 1993 |publicació= Acta Arithmetica
|volum= 63 |pàgines= 313–323}}
* {{ref-web
| autor = Badea, Catalin
| títol = On some criteria for irrationality for series of positive rationals: a survey
| any = 1995
| url = http://www.lacim.uqam.ca/~plouffe/OEIS/citations/caen.pdf
| consulta = 2008-04-18
| arxiuurl = https://web.archive.org/web/20080911223925/http://www.lacim.uqam.ca/~plouffe/OEIS/citations/caen.pdf
| arxiudata = 2008-09-11
}}
* {{ref-publicació
|autor= Boyer, Charles P.; Galicki, Krzysztof; Kollár, János
|títol= Einstein metrics on spheres
|publicació= Annals of Mathematics
|volum= 162
|exemplar= 1
|any= 2005
|pàgines= 557–580
|id= {{arxiv | archive = math.DG | id = 0309408}}
|url= http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.annm/1134073591
}} MR [http://www.ams.org/mathscinet-getitem?mr=2178969 2178969]
* {{ref-publicació
|autor= Brenton, Lawrence and Hill, Richard
|títol= On the Diophantine equation 1=Σ1/''n''<sub>''i''</sub> + 1/Π''n''<sub>''i''</sub> and a class of homologically trivial complex surface singularities
|publicació= Pacific Journal of Mathematics
|url= http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102689567
|volum= 133
|exemplar= 1
|any= 1988
|pàgines= 41–67
|id= MR [http://www.ams.org/mathscinet-getitem?mr=0936356 0936356]
}}
* {{ref-publicació| cognom = Brown |nom=D. J
| article = A lower bound for on-line one-dimensional bin packing algorithms
| exemplar = Tech. Rep. R-864
| data = 1979 | publicació = Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign}}
* {{ref-publicació
|autor= Curtiss, D. R.
|títol= On Kellogg's diophantine problem
|publicació= American Mathematical Monthly
|url= http://www.jstor.org/view/00029890/di991049/99p2492v/0
|volum= 29
|any= 1922
|pàgines= 380–387
}}
* {{ref-publicació
|autor= Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei
|títol= Non-uniqueness and radius of cyclic unary NFAs
|publicació= International Journal of Foundations of Computer Science
|volum= 16
|exemplar= 5
|pàgines= 883–896
|any= 2005
|url= http://www.cs.umanitoba.ca/~mdomarat/pubs/DESW_dcfs.ps
|id= MR [http://www.ams.org/mathscinet-getitem?mr=2174328 2174328]
|doi= 10.1142/S0129054105003352
}}
* {{ref-llibre | autor = [[Paul Erdős|Erdős, Paul]]; Graham, Ronald L
| any = 1980
| títol = Old and new problems and results in combinatorial number theory
| editorial = Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève
| id = MR [http://www.ams.org/mathscinet-getitem?mr=0592420 0592420]}}
* {{ref-publicació|autor= Galambos, Gábor; Woeginger, Gerhard J.
|títol= On-line bin packing — A restricted survey
|publicació= Mathematical Methods of Operations Research
|volum= 42
|exemplar= 1 |any= 1995
| doi = 10.1007/BF01415672
| id = MR [http://www.ams.org/mathscinet-getitem?mr=1346486 1346486]}}
* {{ref-publicació|autor= Golomb, Solomon W.|títol= On certain nonlinear recurring sequences|any= 1963|publicació= American Mathematical Monthly|volum= 70|exemplar= 4|pàgines= 403–405|url= http://www.jstor.org/view/00029890/di991478/99p1225u/0|id= MR [http://www.ams.org/mathscinet-getitem?mr=0148605 0148605]}}
* {{ref-llibre| autor = Graham, R.; [[Donald Knuth|Knuth, D. E.]]; Patashnik, O.| títol = Concrete Mathematics|edició=2a edició| any = 1989| editorial = Addison-Wesley| pàgines = Exercise 4.37| isbn = 0-201-55802-5}}
* {{ref-publicació|autor= Jones, Rafe|títol= The density of prime divisors in the arithmetic dynamics of quadratic polynomials |volum=78 |any=2008 |edició=2 |pàgines=523-544 |publicació=J. Lond. Math. Soc. |arxiv=math.NT/0612415 |doi=10.1112/jlms/jdn034}}
* {{ref-publicació|autor= Liang, Frank M.|títol= A lower bound for on-line bin packing|any= 1980|publicació= Information Processing Letters|volum= 10 |exemplar= 2 |pàgines= 76–79| id = MR [http://www.ams.org/mathscinet-getitem?mr=0564503 0564503]| doi = 10.1016/S0020-0190(80)90077-0}}
* {{ref-publicació|autor= Miller, G. A.|títol= Groups possessing a small number of sets of conjugate operators|publicació= Transactions of the American Mathematical Society|any= 1919|volum= 20|exemplar= 3|pàgines= 260–270|url= http://www.jstor.org/view/00029947/di962842/96p0139s/0}}
* {{ref-publicació|autor= Rosenman, Martin|títol= Problem 3536|publicació= American Mathematical Monthly|volum= 40|exemplar= 3|any= 1933|pàgines= 180|url= http://www.jstor.org/view/00029890/di991156/99p06113/0}}
* {{ref-publicació|autor= Salzer, H. E.|publicació= American Mathematical Monthly|any= 1947|títol= The approximation of numbers as sums of reciprocals|volum= 54|exemplar= 3|pàgines= 135–142|url= http://www.jstor.org/view/00029890/di991304/99p0855u/0|id= MR [http://www.ams.org/mathscinet-getitem?mr=0020339 0020339]}}
* {{ref-publicació|autor= Seiden, Steven S.; Woeginger, Gerhard J.|títol= The two-dimensional cutting stock problem revisited
|publicació= Mathematical Programming|volum= 102|exemplar= 3|any= 2005|pàgines= 519–530| doi = 10.1007/s10107-004-0548-1| id = MR [http://www.ams.org/mathscinet-getitem?mr=2136225 2136225]}}
* {{ref-publicació|autor= Sylvester, J. J.|enllaçautor= J. J. Sylvester|títol= On a point in the theory of vulgar fractions|url= http://www.jstor.org/view/00029327/di994061/99p0133w/0|publicació= American Journal of Mathematics|volum= 3|exemplar= 4|any= 1880|pàgines= 332–335}}
* {{ref-llibre| autor = Vardi, Ilan| títol = Computational Recreations in Mathematica| any = 1991| editorial = Addison-Wesley| pàgines = 82–89| isbn = 0-201-52989-0}}
{{refend}}

== Enllaços externs ==
* [http://www.mathpages.com/home/kmath455.htm Irrationality of Quadratic Sums] {{Webarchive|url=https://web.archive.org/web/20000516205029/http://mathpages.com/home/kmath455.htm |date=2000-05-16}}, a les MathPages de K. S. Brown.
* {{mathworld | title = Sylvester's Sequence | urlname = SylvestersSequence}}

{{ORDENA:Sequencia De Sylvester}}
[[Categoria:Seqüències d'enters]]