Secvența Sylvester

Secvența Sylvester este o secvență întreagă în care fiecare membru succesiv este egal cu produsul membrilor anteriori plus unu. Primii câțiva membri ai secvenței sunt:

2 , 3 , 7 , 43 , 1807, 3263443, 10650056950807, 113423713055421850000000000, … (secvența A000058 în OEIS ).

Numit după James Sylvester , care l - a explorat pentru prima dată în 1880 . Valorile termenilor săi cresc ca exponentul dublu , iar suma termenilor reciproci formează o serie de fracții ale unuia care converg la 1 mai repede decât orice altă serie de fracții ale unuia cu același număr de termeni. Relația de recurență , care definește termenii șirului, permite ca numerele din șir să fie factorizate mai ușor decât alte numere de același ordin, dar datorită creșterii foarte rapide a termenilor seriei, o factorizare completă în prime factorii este cunoscut doar pentru unii membri ai acestei secvențe. Valorile obținute folosind această secvență sunt folosite pentru a forma reprezentarea finală a lui 1 ca fracție egipteană , varietate Sasakian Einstein și ca sursă de date pentru algoritmi online .

Definiții formale

Formal, secvența Sylvester poate fi definită prin formula:

s_{n}=1+\prod _{i=0}^{n-1}s_{i)

Produsul elementelor mulțimii goale este egal cu 1, deci. $s_{0}=2$

O altă modalitate de a defini o secvență este cu o relație de recurență :

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

, unde .

s_{0}=2

Echivalența definițiilor este dovedită prin inducție directă.

Formula generală și asimptotice

Termenii secvenței Sylvester cresc cu viteza exponentului dublu . În special, se poate demonstra că:

s_{n}=\left\rfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,

unde numărul este de aproximativ 1,264084735305302 [1] . Această formulă conduce la următorul algoritm : $E$

s 0 este cel mai apropiat număr întreg de E 2 ; s1 este cel mai apropiat număr întreg de E4 ; s2 este cel mai apropiat număr întreg de E8 ; pentru s n , luați E 2 , pătrați -l de n ori și luați cel mai apropiat număr întreg.

Acest algoritm ar fi acceptabil dacă am avea o modalitate mai bună de a calcula E în loc de a calcula s n și apoi de a calcula rădăcini pătrate .

Creșterea elementelor secvenței Sylvester la o rată dublă exponențială nu este deloc surprinzătoare în comparație cu șirul numerelor Fermat F n . Numerele Fermat sunt adesea date prin formula exponentului dublu , dar pot fi date și prin formule de înmulțire similare cu cele ale secvenței Sylvester: $2^{{2^{n}}}+1$

F_{n}=2+\prod _{i=0}^{n-1}F_{i}.

Legătura cu fracțiile egiptene

Fracțiile de unitate , formate din numere reciproce cu valorile șirului Sylvester, formează o serie infinită :

\sum _{i=0}^{\infty }{\frac {1}{s_{i)}}={\frac {1}{2)}+{\frac {1}{3} }+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .

Sumele parțiale ale acestei serii au forma simplă

\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={ \frac {s_{j}-2}{s_{j}-1}}.

Acest lucru poate fi demonstrat prin inducție sau direct notând că recursiunea implică

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

Astfel, suma rândului telescopic va fi egală cu

\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}}.

Deoarece șirul sumelor parțiale ( s j −2)/( s j −1) converge la 1, întreaga serie formează o reprezentare infinită a fracțiunii egiptene de 1 :

1={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{ \frac {1}{1807}}+\cdots .

Se pot găsi reprezentările finale ale unității ca o fracție egipteană de orice lungime prin încheierea acestei serii și scăderea uneia din ultimul numitor:

1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{6}},\quad 1={\tfrac {1}{2} ))+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{42}},\quad 1={\tfrac {1}{2}} +{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{43}}+{\tfrac {1}{1806}},\quad \dots .

Suma primilor k termeni ai unei serii infinite dă cea mai apropiată limită inferioară a unității în fracțiile egiptene cu k termeni. [2] De exemplu, primii patru termeni sunt adăugați la 1805/1806, astfel încât orice fracție egipteană din intervalul deschis (1805/1806.1) necesită cel puțin cinci termeni.

Se poate gândi la secvența Sylvester ca rezultatul unui algoritm lacom pentru fracțiile egiptene , care la fiecare pas alege cel mai mic divizor posibil care lasă suma parțială mai mică de unu. De asemenea, termenii seriei după primul pot fi considerați ca divizori ai aproximării lacome prin numere impare a numărului 1/2.

Unicitatea seriei cu creștere rapidă cu sume raționale

După cum a observat însuși Sylvester, secvența Sylvester pare să fie singura care are o astfel de rată de creștere, convergând în același timp către un număr rațional. Această secvență arată un exemplu că rata de creștere a unui exponent dublu nu este suficientă pentru ca o secvență de numere întregi să fie o secvență rațională [3] .

Din rezultatul lui Badea [4] rezultă că, dacă o secvență de numere întregi crește suficient de repede încât $un$

a_{n}\geq a_{n-1}^{2}-a_{n-1}+1,

iar dacă rândul

A=\sum {\frac {1}{a_{i)}}

converge către un număr rațional A , atunci pentru tot n , începând de la un loc, această secvență trebuie să satisfacă relația de recurență

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

care poate fi folosit pentru a determina succesiunea Sylvester.

Erdős [5] a presupus că, în rezultatele de acest tip, granița inegalității de creștere a secvenței poate fi înlocuită cu o condiție mai slabă.

\lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.

Divizibilitate și descompunere

Dacă i < j , din definiție rezultă că s j ≡ 1 (mod s i ). Astfel, oricare doi termeni ai secvenței Sylvester sunt coprimi . Secvența poate fi folosită pentru a demonstra infinitatea numărului de numere prime , deoarece orice număr prim poate împărți cel mult un număr din șir. Niciun factor prim al unui număr din șir nu poate fi comparat cu 5 (mod 6), iar secvența poate fi folosită pentru a demonstra că există infinit de numere prime comparabile cu 7 (mod 12). [6]

Probleme nerezolvate la matematică : Toți termenii șirului Sylvester sunt lipsiți de pătrate ?

Rămân multe necunoscute despre factorizarea termenilor secvenței Sylvester. De exemplu, nu se știe dacă toți membrii secvenței sunt fără pătrat , deși toți termenii pentru care se cunoaște factorizarea prime sunt.

După cum scrie Vardi ( 1991 ), este ușor să se determine care dintre termenii șirului Sylvester (dacă există) este divizibil cu un număr prim p - doar se calculează reziduurile termenilor secvenței mod p conform formulei recursive până când zero (mod p ) este întâlnit sau același rest. Folosind această tehnică, Vardy a descoperit că 1166 din primul milion de numere prime sunt divizori ai numerelor Sylvester, [7] și niciun pătrat al acestor numere prime nu împarte numerele Sylvester. Mulțimea numerelor prime care pot fi divizori ai termenilor seriei Sylvester are densitatea zero în mulțimea tuturor primelor. Mai mult decât atât, conform lui Jones [8] , numărul de astfel de numere prime mai mici decât x este egal cu . [9] $O(\pi (x)/\log \log \log x)$

Următorul tabel listează expansiunile cunoscute ale acestor numere (cu excepția primelor patru, care sunt prime): [10]

n	Factori s n
patru	13×139
5	3263443, simplu
6	547×607×1033×31051
7	29881 × 67003 × 9119521 × 6212157481
opt	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 358743802722466241527645691911348949555972560142856914285
zece	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
unsprezece	73 ×C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
paisprezece	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
cincisprezece	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
optsprezece	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
douăzeci	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Aici P n și C n reprezintă numere prime și compuse cu n cifre zecimale.

Aplicații

Boyer, Galicki și Kollár ( Boyer, Galicki, Kollár 2005 ) au folosit proprietățile secvenței Sylvester pentru a defini un număr mare de varietati Sasakian Einstein care au topologia diferențială a sferelor de dimensiuni impare sau a sferelor exotice . Ei au arătat că numărul de metrici Sasakian Einstein diferite pe o sferă topologică de dimensiunea 2 n − 1 este cel puțin proporțional cu s n și, prin urmare, crește cu o rată de dublu exponențial (de la n ).

După cum scriu Galambos și Woeginger ( 1995 ), Brown ( Brown 1979 ) și Liang ( Liang 1980 ) au folosit valori derivate din secvența Sylvester pentru a construi exemple ale unei limite inferioare pentru algoritmii de ambalare a containerelor online . Seiden și Woeginger ( Seiden, Woeginger 2005 ) au folosit în mod similar o secvență pentru limita inferioară de performanță a algoritmului de imbricare 2D [11] .

Problema lui Znam este despre seturi de numere astfel încât fiecare număr din mulțime împarte, dar nu este egal cu, produsul tuturor celorlalte mulțimi plus unu. Fără condiția de echivalență, valorile secvenței Sylvester rezolvă această problemă. Dacă această condiție este stabilită, există o altă soluție obținută dintr-o relație de recurență similară cu definiția secvenței Sylvester. Soluțiile la problema Znam au aplicații la clasificarea punctelor singulare ale suprafețelor (Brenton, Hill 1988) și la teoria automatelor finite nedeterministe . [12]

Curtis ( Curtiss 1922 ) descrie aplicarea celei mai apropiate aproximări a unității prin sume k -termeni ale fracțiilor unității la o limită inferioară a numărului de divizori ai oricărui număr perfect , iar Müller ( Miller 1919 ) folosește aceeași proprietate pentru o valoare mai mică . legat pe numărul unor grupuri .

Vezi și

constanta lui Caen
Număr pseudoperfect simplu

Note

↑ În Graham, Knuth și Patashnik ( 1989 ), această afirmație este dată ca un exercițiu. Vezi și Golomb ( Golomb 1963 ).
↑ Această afirmație este de obicei atribuită lui Curtis ( Curtiss 1922 ), dar Miller ( Miller 1919 ) a făcut aceeași afirmație într-o lucrare anterioară. Vezi și Rosenman și Underwood 1933 , Salzer 1947 și ( Soundararajan 2005 ).
↑ Guy, 2004 .
↑ ( Badea 1993 )
↑ ( Erdős 1980 ), pentru o trecere în revistă a lucrărilor pe această ipoteză - ( Badea 1995 ), vezi și Brown, 1979 .
↑ Guy, Nowakowski, 1975 .
↑ Se pare că există o greșeală de tipar aici, deoarece Andersen a găsit 1167 de divizori primi în acest interval.
↑ Jones, 2006 .
↑ Odoni, 1985 .
↑ Toți factorii primi p ai numerelor Sylvester s n cu p < 5⋅10 7 și n ≤ 200 sunt enumerați de Vardy. Ken Takusagawa a enumerat extinderile de până la s 9 Arhivat 25 decembrie 2014 la Wayback Machine și extinderile s 10 Arhivat 25 decembrie 2014 la Wayback Machine . Expansiunile rămase sunt preluate din lista de expansiuni ale secvenței Sylvester Arhivată 29 noiembrie 2014 la Wayback Machine , întreținută de Jens Kruse Andersen. Din 13.06.2014.
↑ În lucrarea lor, Seiden și Voginger se referă la secvența Sylvester ca „secvența Salzer”, bazându-se pe lucrarea lui Salzer ( Salzer 1947 ) privind cea mai apropiată aproximare.
↑ Domaratzki, Ellul, Shallit, Wang, 2005 .

Literatură

Catalin Badea. O teoremă despre iraționalitatea serii infinite și aplicații // Acta Arithmetica . - 1993. - T. 63 . - S. 313-323 .
Badea, Catalin. Pe unele criterii de iraționalitate pentru serii de raționalități pozitive: un sondaj (engleză) . — 1995.
Charles P. Boyer, Krzysztof Galicki, János Kollár. Metrica Einstein pe sfere // Analele matematicii . - 2005. - T. 162 , nr. 1 . - S. 557-580 . - doi : 10.4007/annals.2005.162.557 . — arXiv : math.DG/0309408 .
Lawrence Brenton, Richard Hill. Pe ecuația diofantină 1=Σ1/ n i + 1/Π n i și o clasă de singularități de suprafață complexe omologic triviale // Pacific Journal of Mathematics . - 1988. - T. 133 , nr. 1 . - S. 41-67 . - doi : 10.2140/pjm.1988.133.41 .
DJ Brown. O limită inferioară pentru algoritmii on-line de împachetare a containerelor unidimensionale. — Laboratorul de Științe Coordonate, Univ. din Illinois, Urbana-Champaign, 1979. - Vol. Teh. Reprezentant. R-864 .
D. R. Curtis. Despre problema diofantică a lui Kellogg // American Mathematical Monthly . - 1922. - T. 29 , nr. 10 . - S. 380-387 . - doi : 10.2307/2299023 . — .
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Non-unicitatea și raza NFA-urilor unare ciclice // International Journal of Foundations of Computer Science. - 2005. - T. 16 , nr. 5 . - S. 883-896 . - doi : 10.1142/S0129054105003352 .
Paul Erdős, Ronald L. Graham. Probleme vechi și noi și rezultate în teoria numerelor combinatorii. — Monographies de L'Enseignement Mathematique, nr. 28, Univ. de Geneve, 1980.
Gábor Galambos, Gerhard J. Woeginger. Ambalare on-line a coșului - Un sondaj restricționat // Metode matematice de cercetare operațională. - 1995. - Vol. 42 , iss. 1 . — P. 25 . - doi : 10.1007/BF01415672 .
Solomon W. Golomb. Pe anumite secvențe recurente neliniare // American Mathematical Monthly. - 1963. - T. 70 , nr. 4 . - S. 403-405 . - doi : 10.2307/2311857 . — .
R. Graham, D.E. Knuth, O. Patashnik. Matematică concretă. — al 2-lea. - Addison-Wesley, 1989. - ISBN 0-201-55802-5 .
Richard K Guy. Probleme nerezolvate în teoria numerelor. — al 3-lea. - Springer-Verlag , 2004. - P. 346. - ISBN 0-387-20860-7 .
Richard Guy, Richard Nowakowski. Descoperirea primelor cu Euclid // Delta (Waukesha). - 1975. - V. 5 , nr. 2 . - S. 49-63 .
Rafe Jones. Densitatea divizorilor primi în dinamica aritmetică a polinoamelor pătratice . - 2006. - arXiv : math.NT/0612415 .
Frank M. Liang. O limită inferioară pentru ambalarea on-line în coș // Scrisori de procesare a informațiilor. - 1980. - T. 10 , nr. 2 . - S. 76-79 . - doi : 10.1016/S0020-0190(80)90077-0 .
GA Miller. Grupuri care posedă un număr mic de seturi de operatori conjugați // Tranzacții ale Societății Americane de Matematică . - 1919. - Vol. 20 , iss. 3 . - P. 260-270 . - doi : 10.2307/1988867 . — .
RWK Odoni. Pe divizorii primi ai șirului w n+1 =1+w 1 ⋯ w n // J. Lond. Matematică. Soc., II. Ser.. - 1985. - T. 32 . - S. 1-11 .
Martin Rosenman, F. Underwood. Problema 3536 // American Mathematical Monthly. - 1933. - T. 40 , nr. 3 . - S. 180-181 . — .
S.E. Salzer. Aproximarea numerelor ca sume de reciproce // American Mathematical Monthly. - 1947. - T. 54 , nr. 3 . - S. 135-142 . - doi : 10.2307/2305906 . — .
Steven S. Seiden, Gerhard J. Woeginger. Problema materialului de tăiere bidimensional revăzută // Programare matematică. - 2005. - T. 102 , nr. 3 . - S. 519-530 . - doi : 10.1007/s10107-004-0548-1 .
K. Soundarajan. Aproximând 1 de jos folosind n fracții egiptene. - 2005. - arXiv : math.CA/0502247 .
JJ Sylvester. Pe un punct din teoria fracțiilor vulgare // American Journal of Mathematics . - 1880. - T. 3 , nr. 4 . - S. 332-335 . - doi : 10.2307/2369261 . — .
Ilan Vardi. Recreeri computaționale în Mathematica. - Addison-Wesley, 1991. - S. 82-89. - ISBN 0-201-52989-0 .

Link -uri

Iraționalitatea sumelor cuadratice, din MathPages lui KS Brown.
Weisstein, Eric W. Sylvester's Sequence (engleză) pe site-ul Wolfram MathWorld .