Seqüència de Sylvester

De Viquipèdia
Salta a la navegació Salta a la cerca
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 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 la unitat.

Definicions formals[modifica]

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

with s0 = 2.

Es pot demostrar per inducció que totes dues definicions són equivalents.

Relació amb les fraccions egipcianes[modifica]

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ó dóna

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 dóna 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 u. 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[modifica]

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 E2; s1 és l'enter més proper a E4; s2 és l'enter més proper a E8; per a sn, preneu E2, 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[modifica]

Com Sylvester mateix observà, la seqüència de Sylvester sembla ser 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[modifica]

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[modifica]

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[modifica]

  1. Aquesta afirmació se sol atribuir a Curtiss (1922), però Miller (1919) sembla que féu la mateixa afirmació en una publicació anterior. Vegeu també Rosenman (1933), Salzer (1947), i Soundararajan (2005).
  2. Graham, Knuth, and Patashnik (1989) ho proposen com a exercici; vegeu també Golomb (1963).
  3. (això sembla ser un error, ja que Andersen troba 1167 divisors primers en aquest marge)
  4. Tots els factors primers p dels nombres de Sylvester 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 Sylvester's sequence que manté Jens Kruse Andersen, consultada el 2 d'october de 2007.
  5. 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[modifica]

Enllaços externs[modifica]