Sylvester sorozat

A Sylvester sorozat egy egész sorozat , amelyben minden egymást követő tag egyenlő az előző tagok plusz egy szorzatával. A sorozat első néhány tagja:

2 , 3 , 7 , 43 , 1807, 3263443, 10650056950807, 113423713055421850000000000, … ( A000058 sorozat az OEIS -ben ).

James Sylvesterről nevezték el , aki először 1880 -ban fedezte fel . Tagjainak értékei úgy nőnek, mint a dupla kitevő , és a reciprok tagok összege egy törtsorozatot képez , amely gyorsabban konvergál 1-hez, mint bármely más törtsorozat ugyanannyi taggal. Az ismétlődési reláció , amely meghatározza a sorozat tagjait, lehetővé teszi a sorozatban lévő számok egyszerűbb faktorálását , mint más azonos sorrendű számok, de a sorozat tagjainak nagyon gyors növekedése miatt teljes faktorizálást prímmá faktorok csak e sorozat néhány tagja esetében ismertek. Az ezzel a szekvenciával kapott értékeket az 1 egyiptomi törtként , a Sasakian Einstein-sokaságok végső reprezentációjának kialakításához, valamint az online algoritmusok adatforrásaként használjuk .

Formális definíciók

Formálisan a Sylvester sorozat a következő képlettel definiálható:

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

üres halmaz elemeinek szorzata egyenlő 1-gyel, tehát. $s_{0}=2$

A sorozat meghatározásának másik módja az ismétlődési reláció :

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

, hol .

s_{0}=2

A definíciók egyenértékűségét direkt indukció bizonyítja.

Általános képlet és aszimptotika

A Sylvester sorozat tagjai a kettős kitevő sebességével nőnek . Konkrétan kimutatható, hogy:

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

ahol a szám hozzávetőlegesen 1,264084735305302 [1] . Ez a képlet a következő algoritmushoz vezet : $E$

s 0 az E 2 -hez legközelebbi egész szám ; s 1 az E 4 -hez legközelebbi egész szám ; s 2 az E 8 -hoz legközelebbi egész szám ; s n esetén vegyük E 2 -t, n -szer négyzetre emeljük , és vegyük a legközelebbi egész számot.

Ez az algoritmus elfogadható lenne, ha jobb módszerünk lenne az E kiszámítására az s n , majd a négyzetgyök kiszámítása helyett .

A Sylvester sorozat elemeinek kétszeres exponenciális növekedése egyáltalán nem meglepő, ha összehasonlítjuk az F n Fermat-számok sorozatával . A Fermat-számokat gyakran a kettős kitevő képlettel adják meg , de a Sylvester sorozathoz hasonló szorzóképletekkel is megadhatók: $2^{{2^{n}}}+1$

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

Kapcsolat az egyiptomi frakciókkal

Az egység törtrészei , amelyeket a Sylvester sorozat értékeivel reciprok számok alkotnak, végtelen sorozatot alkotnak :

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

Ennek a sorozatnak a részösszegei egyszerű formában vannak

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

Ez igazolható indukcióval vagy közvetlenül a rekurzió implikálásával

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

Így a teleszkópos sor összege egyenlő lesz

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

Mivel a ( s j −2)/( s j −1) részösszegek sorozata 1-hez konvergál, az egész sorozat az 1 végtelen egyiptomi tört reprezentációját alkotja :

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

Az egység végső reprezentációját egy tetszőleges hosszúságú egyiptomi törtként találhatjuk meg, ha ezt a sorozatot befejezzük, és az utolsó nevezőből levonunk egyet:

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 .

Egy végtelen sorozat első k tagjának összege adja meg a legközelebbi alsó korlátot a k tagú egyiptomi törtek egységére. [2] Például az első négy tag hozzáadódik az 1805/1806-hoz, tehát a nyitott intervallumban (1805/1806.1) lévő bármely egyiptomi törthez legalább öt tagra van szükség.

A Sylvester sorozatot egy egyiptomi törtek mohó algoritmusának eredményeként lehet elképzelni , amely minden lépésben kiválasztja a lehető legkisebb osztót, amely a részösszeget egynél kisebbre hagyja. Valamint az első utáni sorozat tagjait tekinthetjük az 1/2 szám páratlan számainak való mohó közelítésének osztóinak.

Gyorsan növekvő sorozatok egyedisége racionális összegekkel

Ahogy Sylvester maga is megjegyezte, úgy tűnik, hogy a Sylvester sorozat az egyetlen, amelynek ilyen növekedési üteme van, miközben konvergál egy racionális számhoz. Ez a sorozat egy példát mutat arra, hogy a kettős kitevő növekedési üteme nem elegendő ahhoz, hogy egy egész számok sorozata racionális sorozat legyen [3] .

Badea eredményéből [4] az következik , hogy ha egy egész számsor elég gyorsan növekszik ahhoz, hogy $a_n$

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

és ha a sor

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

konvergál egy A racionális számhoz , akkor minden n esetén, valahonnan kiindulva ennek a sorozatnak ki kell elégítenie az ismétlődési relációt

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

amelyek segítségével meghatározható a Sylvester szekvencia.

Erdős [5] azt sejtette , hogy az ilyen típusú eredményekben a szekvencia növekedési egyenlőtlenségének határa helyettesíthető egy gyengébb feltétellel.

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

Oszthatóság és dekompozíció

Ha i < j , akkor a definícióból következik, hogy s j ≡ 1 (mod s i ). Így a Sylvester sorozat bármely két tagja koprím . A sorozat felhasználható a prímszámok végtelenségének bizonyítására , mivel bármely prímszám legfeljebb egy számot oszthat a sorozatban. A sorozatban szereplő szám egyik prímtényezője sem hasonlítható össze 5-tel (6. mód), és a sorozat felhasználható annak bizonyítására, hogy végtelenül sok a 7-tel összehasonlítható prímszám (mod 12). [6]

Megoldatlan matematikai problémák : A Sylvester sorozat minden tagja mentes a négyzetektől ?

Sok ismeretlen maradt a Sylvester-sorozat tagjainak faktorizálásával kapcsolatban. Például nem ismert, hogy a sorozat minden tagja négyzetmentes- e , bár minden olyan tag, amelyre ismert a prímtényezők száma, igen.

Ahogy Vardi ( 1991 ) írja, könnyű meghatározni, hogy a Sylvester sorozat tagjai közül (ha van) melyik osztható p prímszámmal - csak számolja ki a mod p sorozat tagjainak maradékait a rekurzív képlet szerint, amíg nulla (mod p ) vagy ugyanaz a maradék. Ezzel a technikával Vardy azt találta, hogy az első millió prímből 1166 osztója a Sylvester-számoknak, [7] és e prímszámok négyzete sem osztja a Sylvester-számokat. A Sylvester sorozat tagjainak osztóinak számító prímek halmazának sűrűsége nulla az összes prímszám halmazában. Ráadásul Jones [8] szerint az x - nél kisebb prímszámok száma egyenlő . [9] $O(\pi (x)/\log \log \log x)$

A következő táblázat felsorolja ezeknek a számoknak az ismert bővítéseit (az első négy kivételével, amelyek prímszámúak): [10]

n	Tényezők s n
négy	13×139
5	3263443, egyszerű
6	547×607×1033×31051
7	29881 × 67003 × 9119521 × 6212157481
nyolc	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 3587438027224662415276456919113489495597256044281911348949559725604242569138728
tíz	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
tizenegy	73 ×C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
tizennégy	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
tizenöt	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
tizennyolc	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
húsz	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Itt P n és C n n tizedesjegyű prím- és összetett számokat jelöl.

Alkalmazások

Boyer, Galicki és Kollár ( Boyer, Galicki, Kollár 2005 ) a Sylvester sorozat tulajdonságait felhasználva nagyszámú Sasakian Einstein sokaságot határoztak meg , amelyek páratlan dimenziós gömbök vagy egzotikus gömbök differenciális topológiájával rendelkeznek . Megmutatták, hogy a 2 n − 1 dimenziójú topológiai gömbön a különböző Sasakian Einstein- metrikák száma legalább arányos s n -nel , ezért kétszeres exponenciális sebességgel nő ( n -től ).

Ahogy Galambos és Woeginger ( 1995 ) írja, Brown ( Brown 1979 ) és Liang ( Liang 1980 ) a Sylvester szekvenciából származó értékeket használta, hogy példákat hozzon létre az online konténercsomagoló algoritmusok alsó határára . Seiden és Woeginger ( Seiden, Woeginger 2005 ) hasonlóan egy szekvenciát használt a 2D egymásba ágyazási algoritmus alsó teljesítményhatárára [11] .

Znam problémája olyan számhalmazokról szól, hogy a halmazban lévő minden szám osztja, de nem egyenlő az összes többi halmaz plusz egy szorzatával. Az ekvivalencia feltétel nélkül a Sylvester sorozatértékek megoldják ezt a problémát. Ha ez a feltétel be van állítva, akkor van egy másik megoldás, amelyet a Sylvester sorozat definíciójához hasonló ismétlődési relációból kapunk. A Znam-probléma megoldásai alkalmazhatók a felületek szinguláris pontjainak osztályozására (Brenton, Hill 1988) és a nemdeterminisztikus véges automaták elméletére . [12]

Curtis ( Curtiss 1922 ) leírja az egységhez legközelebbi közelítés alkalmazását az egység törteinek k -tagú összegével bármely tökéletes szám osztóinak alsó korlátjára , Müller ( Miller 1919 ) pedig ugyanezt a tulajdonságot használja egy alacsonyabb értékre . kötött egyes csoportok számához .

Lásd még

Caen állandó
Egyszerű pszeudoperfect szám

Jegyzetek

↑ Graham, Knuth és Patashnik ( 1989 ) ezt az állítást gyakorlatként adják meg. Lásd még: Golomb ( Golomb 1963 ).
↑ Ezt az állítást általában Curtisnek tulajdonítják ( Curtiss 1922 ), de Miller ( Miller 1919 ) ugyanezt az állítást tette egy korábbi munkájában. Lásd még Rosenman és Underwood 1933 , Salzer 1947 és ( Soundararajan 2005 ).
↑ Srác, 2004 .
↑ ( Badea 1993 )
↑ ( Erdős 1980 ), ezzel a hipotézissel foglalkozó munkák áttekintését - ( Badea 1995 ), lásd még Brown, 1979 .
↑ Guy, Nowakowski, 1975 .
↑ Úgy tűnik, itt elírás van, mivel Andersen 1167 prímosztót talált ebben a tartományban.
↑ Jones, 2006 .
↑ Odoni, 1985 .
↑ Az s n Sylvester-számok összes p prímtényezőjét , ahol p < 5⋅10 7 és n ≤ 200, Vardy felsorolja. Ken Takusagawa felsorolta az s 9 -ig terjedő bővítményeket Archivált 2014. december 25-én a Wayback Machine -nél és az s 10 -es bővítményeket Archivált 2014. december 25-én a Wayback Machine -nél . A fennmaradó bővítések a Sylvester sorozat bővítményeinek listájából származnak . Archiválva : 2014. november 29. a Wayback Machine -nél , amelyet Jens Kruse Andersen tart fenn. 2014.06.13-án.
↑ Seiden és Voginger tanulmányukban a Sylvester-szekvenciát "Salzer-szekvenciaként" említik, Salzer munkájára ( Salzer 1947 ) építve a legközelebbi közelítéssel.
↑ Domaratzki, Ellul, Shallit, Wang, 2005 .

Irodalom

Badea Katalin. Tétel a végtelen sorozatok és alkalmazások irracionalitásáról // Acta Arithmetica . - 1993. - T. 63 . - S. 313-323 .
Badea, Catalin. Az irracionalitás egyes kritériumairól pozitív racionalitások sorozatára: felmérés (angolul) . – 1995.
Charles P. Boyer, Krzysztof Galicki, János Kollár. Einstein-metrikák gömbökön // Annals of Mathematics . - 2005. - T. 162 , sz. 1 . - S. 557-580 . - doi : 10.4007/annals.2005.162.557 . — arXiv : math.DG/0309408 .
Lawrence Brenton, Richard Hill. Az 1=Σ1/ n i + 1/Π n i diofantusi egyenletről és a homológiailag triviális komplex felületi szingularitások osztályáról // Pacific Journal of Mathematics . - 1988. - T. 133 , sz. 1 . - S. 41-67 . - doi : 10.2140/pjm.1988.133.41 .
DJ Brown. Alsó korlát az on-line egydimenziós tárolóedény-csomagoló algoritmusokhoz. — Koordinált Tudományos Lab., Univ. Illinois, Urbana-Champaign, 1979 . Tech. Ismétlés. R-864 .
D. R. Curtis. A Kellogg-diofantin problémáról // American Mathematical Monthly . - 1922. - T. 29 , sz. 10 . - S. 380-387 . - doi : 10.2307/2299023 . — .
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Ciklikus unáris NFA-k nem egyedisége és sugara // International Journal of Foundations of Computer Science. - 2005. - T. 16 , sz. 5 . - S. 883-896 . - doi : 10.1142/S0129054105003352 .
Erdős Paul, Ronald L. Graham. Régi és új problémák és eredmények a kombinatorikus számelméletben. – Monographies de L'Enseignement Mathematique, 3. sz. 28, Univ. de Geneve, 1980.
Galambos Gábor, Gerhard J. Woeginger. On-line szemetescsomagolás – korlátozott felmérés // Műveletek kutatásának matematikai módszerei. - 1995. - 1. évf. 42 , iss. 1 . — 25. o . - doi : 10.1007/BF01415672 .
Solomon W. Golomb. Bizonyos nemlineárisan ismétlődő szekvenciákon // American Mathematical Monthly. - 1963. - T. 70 , sz. 4 . - S. 403-405 . - doi : 10.2307/2311857 . — .
R. Graham, D. E. Knuth, O. Patashnik. Konkrét matematika. — 2. - Addison-Wesley, 1989. - ISBN 0-201-55802-5 .
Richard K Guy. Megoldatlan problémák a számelméletben. — 3. - Springer-Verlag , 2004. - P. 346. - ISBN 0-387-20860-7 .
Richard Guy, Richard Nowakowski. Prímszámok felfedezése Euklidész segítségével // Delta (Waukesha). - 1975. - V. 5 , sz. 2 . - S. 49-63 .
Rafe Jones. A prímosztók sűrűsége a másodfokú polinomok aritmetikai dinamikájában . - 2006. - arXiv : math.NT/0612415 .
Frank M. Liang. Alsó korlát az on-line kukák csomagolásához // Információfeldolgozási levelek. - 1980. - T. 10 , sz. 2 . - S. 76-79 . - doi : 10.1016/S0020-0190(80)90077-0 .
GA Miller. Csoportok, amelyek kis számú konjugált operátorkészlettel rendelkeznek // Transactions of the American Mathematical Society . - 1919. - 1. évf. 20 , iss. 3 . - 260-270 . - doi : 10.2307/1988867 . — .
RWK Odoni. A sorozat prímosztóin w n+1 =1+w 1 ⋯ w n // J. Lond. Math. Szoc., II. Szer.. - 1985. - T. 32 . - S. 1-11 .
Martin Rosenman, F. Underwood. 3536. feladat // American Mathematical Monthly. - 1933. - T. 40 , sz. 3 . - S. 180-181 . — .
H. E. Salzer. A számok közelítése reciprok összegeként // American Mathematical Monthly. - 1947. - T. 54 , sz. 3 . - S. 135-142 . - doi : 10.2307/2305906 . — .
Steven S. Seiden, Gerhard J. Woeginger. A kétdimenziós forgácsolóanyag probléma újragondolása // Matematikai programozás. - 2005. - T. 102 , sz. 3 . - S. 519-530 . - doi : 10.1007/s10107-004-0548-1 .
K. Soundarajan. 1-et alulról közelítve n egyiptomi tört felhasználásával. - 2005. - arXiv : math.CA/0502247 .
JJ Sylvester. A vulgáris törtek elméletének egy pontjáról // American Journal of Mathematics . - 1880. - T. 3 , sz. 4 . - S. 332-335 . - doi : 10.2307/2369261 . — .
Ilan Vardi. Számítógépes kikapcsolódás a Mathematicában. - Addison-Wesley, 1991. - S. 82-89. - ISBN 0-201-52989-0 .

Linkek

A másodfokú összegek irracionalitása , KS Brown MathPages oldaláról.
Weisstein, Eric W. Sylvester's Sequence (angolul) a Wolfram MathWorld weboldalán .