Seqüència de Sylvester
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Sylvester-square.svg/220px-Sylvester-square.svg.png)
En teoria dels nombres, la seqüència de Sylvester és una seqüència d'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: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (successió A000058 a l'OEIS).
La seqüència de Sylvester pren el nom de James Joseph Sylvester, qui la investigà per primera vegada el 1880. Els seus valors creixen doblement exponencialment, i la suma dels seus recíprocs forma una sèrie de 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ó 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 fraccions egipcianes de suma 1, així com en varietats saskianes i les d'Einstein.
Definicions formals
Formalment, la seqüència de Sylvester es pot definir per la fórmula
El producte d'un conjunt buit és 1, car s0 = 2.
Altrament, es pot definir la seqüència per la recurrència
- amb s0 = 2.
Es pot demostrar per inducció que totes dues definicions són equivalents.
Relació amb les fraccions egipcianes
Les fraccions unitàries formades pels recíprocs dels valors de la seqüència de Sylvester generen una sèrie infinita:
Les sumes parcials d'aquesta sèrie tenen una forma simple,
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
com es volia demostrar. Atès que aquesta seqüència de sumes parcials (sj-2)/(sj-1) convergeix a u, la sèrie global forma una representació en fracció egipciana infinita del nombre u:
Es poden trobar representacions de la unitat en fraccions egipcianes finites, de qualsevol longitud, truncant aquesta sèrie i restant u del darrer denominador:
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.[1] 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 doblement exponencialment com a funció de n. En particular, es pot demostrar que
per a un nombre E que és aproximadament 1.264.[2] Aquesta fórmula fa l'efecte de l'algorisme següent:
- s0 és l'enter més proper a E²; s1 és l'enter més proper a E4; s₂ és l'enter més proper a E8; per a sn, 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 sn 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 nombres de Fermat Fn; els nombres de Fermat es defineixen habitualment amb una fórmula doblement exponencial, , però també es poden definir amb una fórmula de productes molt semblant a la que defineix la seqüència de Sylvester:
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 creix prou aviat que
i si la sèrie
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
que es pot fer servir per definir la seqüència de Sylvester.
Erdős (1980) 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,
Badea (1995) recull els progressos lligats a aquesta conjectura; vegeu també Brown.
Divisibilitat i factoritzacions
Si i < j, se segueix de la definició que sj ≡ 1 (mod si). 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 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 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.[3] 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):[4]
n | Factors de sn |
---|---|
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, Pn i Cn denoten nombres primers i compostos de n dígits.
Aplicacions
![]() | Aquest article o secció necessita millorar una traducció deficient. Podeu col·laborar-hi si coneixeu prou la llengua d'origen. També podeu iniciar un fil de discussió per consultar com es pot millorar. Elimineu aquest avís si creieu que està solucionat raonablement. |
Boyer i cols. (2005) fan servir les propietats de la seqüència de Sylvester per definir grans nombres de Sasakian Einstein manifolds que tenen la topologia diferencial d'hiperesferes de dimensió senar o d'esferes exòtiques. Demostren que el nombre de mètriques Sasakian Einstein sobre una esfera topològica de dimensió 2n − 1 is almenys proporcional a sn 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.[5]
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ò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
- ↑ 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).
- ↑ Graham, Knuth, and Patashnik (1989) ho proposen com a exercici; vegeu també Golomb (1963).
- ↑ (això sembla un error, ja que Andersen troba 1167 divisors primers en aquest marge)
- ↑ Tots els factors primers p dels nombres de Sylvester sn amb p < 5×107 i n ≤ 200 són enumerats per Vardi. Ken Takusagawa enumera les factorizations fins a s9 i la factorització de s10. La resta de factoritzacions són d'una llista de factoritzacions de la seqüència de Sylvester Arxivat 2007-09-27 a Wayback Machine. que manté Jens Kruse Andersen, consultada el 2 d'octubre de 2007.
- ↑ 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.
Bibliografia
- Badea, Catalin «A theorem on irrationality of infinite series and applications». Acta Arithmetica, 63, 1993, pàg. 313–323.
- Badea, Catalin. «On some criteria for irrationality for series of positive rationals: a survey», 1995. Arxivat de l'original el 2008-09-11. [Consulta: 18 abril 2008].
- Boyer, Charles P.; Galicki, Krzysztof; Kollár, János «Einstein metrics on spheres». Annals of Mathematics, 162, 1, 2005, pàg. 557–580. arXiv:math.DG/0309408. MR 2178969
- Brenton, Lawrence and Hill, Richard «On the Diophantine equation 1=Σ1/ni + 1/Πni and a class of homologically trivial complex surface singularities». Pacific Journal of Mathematics, 133, 1, 1988, pàg. 41–67. MR 0936356.
- Brown, D. J «A lower bound for on-line one-dimensional bin packing algorithms». Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign, Tech. Rep. R-864, 1979.
- Curtiss, D. R. «On Kellogg's diophantine problem». American Mathematical Monthly, 29, 1922, pàg. 380–387.
- Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei «Non-uniqueness and radius of cyclic unary NFAs». International Journal of Foundations of Computer Science, 16, 5, 2005, pàg. 883–896. DOI: 10.1142/S0129054105003352. MR 2174328.
- Erdős, Paul; Graham, Ronald L. Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève, 1980. MR 0592420.
- Galambos, Gábor; Woeginger, Gerhard J. «On-line bin packing — A restricted survey». Mathematical Methods of Operations Research, 42, 1, 1995. DOI: 10.1007/BF01415672. MR 1346486.
- Golomb, Solomon W. «On certain nonlinear recurring sequences». American Mathematical Monthly, 70, 4, 1963, pàg. 403–405. MR 0148605.
- Graham, R.; Knuth, D. E.; Patashnik, O.. Concrete Mathematics. 2a edició. Addison-Wesley, 1989, p. Exercise 4.37. ISBN 0-201-55802-5.
- Jones, Rafe «The density of prime divisors in the arithmetic dynamics of quadratic polynomials». J. Lond. Math. Soc., 78, 2, 2008, pàg. 523-544. arXiv: math.NT/0612415. DOI: 10.1112/jlms/jdn034.
- Liang, Frank M. «A lower bound for on-line bin packing». Information Processing Letters, 10, 2, 1980, pàg. 76–79. DOI: 10.1016/S0020-0190(80)90077-0. MR 0564503.
- Miller, G. A. «Groups possessing a small number of sets of conjugate operators». Transactions of the American Mathematical Society, 20, 3, 1919, pàg. 260–270.
- Rosenman, Martin «Problem 3536». American Mathematical Monthly, 40, 3, 1933, pàg. 180.
- Salzer, H. E. «The approximation of numbers as sums of reciprocals». American Mathematical Monthly, 54, 3, 1947, pàg. 135–142. MR 0020339.
- Seiden, Steven S.; Woeginger, Gerhard J. «The two-dimensional cutting stock problem revisited». Mathematical Programming, 102, 3, 2005, pàg. 519–530. DOI: 10.1007/s10107-004-0548-1. MR 2136225.
- Sylvester, J. J. «On a point in the theory of vulgar fractions». American Journal of Mathematics, 3, 4, 1880, pàg. 332–335.
- Vardi, Ilan. Computational Recreations in Mathematica. Addison-Wesley, 1991, p. 82–89. ISBN 0-201-52989-0.
Enllaços externs
- Irrationality of Quadratic Sums Arxivat 2000-05-16 a Wayback Machine., a les MathPages de K. S. Brown.
- Weisstein, Eric W., «Sylvester's Sequence» a MathWorld (en anglès).