Sylvester-sorozat
A számelmélet területén a Sylvester-sorozat vagy Sylvester-féle sorozat olyan egész számokat tartalmazó sorozat, melynek minden tagja az előző tagok összeszorzásával és 1 hozzáadásával képezhető. A sorozat első néhány tagja:
2, 3, 7, 43, 1807, , , 113423713055421844361000443 .

A Sylvester-sorozatot James Joseph Sylvester brit matematikusról nevezték el, aki 1880-ban elsőként tanulmányozta. A sorozat tagjai dupla exponenciális sebességgel nőnek, reciprokainak egységtört-sorösszege pedig gyorsabban tart 1-hez, mint bármely más egységtört-sorozat. A rekurzív definíció lehetővé teszi, hogy a sorozat tagjait a hasonló nagyságrendű számoknál gyorsabban lehessen prímtényezőkre bontani, de a sorozat gyors növekedése miatt így is csak az első néhány tagnak ismert a pontos felbontása. A sorozat felhasználási módjai között van az 1 véges egyiptomi tört-felbontásainak konstruálása, a Szaszaki–Einstein-sokaságok (, ) tagjai és az online algoritmusok keményebb darabjai.

Formális definíciók 
A Sylvester-sorozat formális meghatározása:

Az üres szorzat értéke megegyezés szerint 1, ezért s0 = 2.

Egy másik rekurzív definíció szerint:
 ahol s0 = 2.
Könnyen megmutatható a két definíció egyenértékűsége.

Zárt alak, aszimptotikus viselkedés 
A Sylvester-számok n függvényében dupla exponenciálisan nőnek. Megmutatható, hogy

az E számra, ami körülbelül 1,264084735305302. A képlet hatásában a következő algoritmussal egyezik meg:
s0 az E2-höz legközelebb álló egész szám; s1 az E4-hez legközelebb álló egész szám; s2 az E8-hoz legközelebb álló egész szám; bármely  sn-re, vedd E2-t, emeld négyzetre n-szer és vedd a hozzá legközelebbi egész számot.
Ez akkor lehetne praktikus algoritmus, ha lenne más módja E meghatározásának, mint az  sn kiszámolása és egymás utáni négyzetgyökvonások.

A Sylvester-sorozat dupla exponenciális növekedése nem meglepő, összehasonlítva őket az Fn Fermat-számok sorozatával; a Fermat-számokat általában egy dupla exponenciális képlettel adják meg –  –, de valójában a Sylvester-sorozathoz hasonló módon is megadhatók lennének:

Egyiptomi törtekkel való kapcsolatai 
A Sylvester-sorozat reciprokai által megadott egységtörtek végtelen sora a következő:

A sor részösszegeinek egyszerű alakja:

Ez igazolható indukcióval, vagy közvetlen módon, belátva hogy a rekurzióból következik:

tehát az összegzést teleszkóposan elvégezve:

Mivel a részösszegek ezen (sj-2)/(sj-1) sorozata egyhez konvergál, a teljes sor az 1 szám végtelen egyiptomi tört-reprezentációját adja:

Az 1 bármilyen hosszú egyiptomitört-megfeleltetése megkapható a sorozat „levágásával”, majd az utolsó nevezőből 1 levonásával:

A végtelen sorozat első k tagjának összege adja a legközelebbi lehetséges alsó becslését 1-nek az összes k-tagú egyiptomi törtes sorozat között. Például az első négy tag összege 1805/1806, ezért bármely, az (1805/1806,1) nyílt intervallumban lévő egyiptomitört-megfeleltetés legalább 5 elemet igényel.

A Sylvester-sorozat úgy is felfogható, mint egy egyiptomi törteket előállító mohó algoritmus, ami minden lépésben kiválasztja a lehető legkisebb nevezőt, amitől a sor részösszege még egy alatt marad. Más megközelítésben a sorozat első tagjától tekinthető az ½ páratlan mohó felbontásának.

Egyediség és racionális összegű gyorsan növő sorok 
Amint azt Sylvester maga is megjegyezte, a Sylvester-sorozat egyedinek tűnik abban a tekintetben, hogy ilyen gyorsan növekvő értékek mellett a reciprokok összege racionális számhoz konvergál. A sorozat példát nyújt arra, hogy önmagában a dupla exponenciális növekedés nem elégséges feltétele az irracionalitás-sorozatságnak.

Precízebben, -ból következik, hogy ha egy  sorozat elég gyorsan nő ahhoz, hogy

és az

sorozat egy A racionális számhoz konvergál, akkor egy adott számot elérve minden n számra a sorozatot ugyanaz az

rekurrencia-szabály kell, hogy meghatározza, mint a Sylvester-sorozatot.

 sejtése szerint az ilyen típusú eredményekben a sorozat növekedését korlátozó egyenlőtlenség lecserélhető a következő gyengébb feltételre:

 vizsgálta a sejtés megoldásának előrehaladását; lásd még .

Oszthatóság és prímfelbontások 
Ha i < j, a definícióból következik, hogy sj ≡ 1 (mod si). Ezért a Sylvester-sorozat bármely két tagja relatív prím. A sorozat annak bizonyítására is alkalmas, hogy végtelen sok prímszám létezik, hiszen bármely prímszám a sorozat legfeljebb egy tagjának lehet osztója. Ezen túl, a sorozat tagjainak egyetlen prímtényezője sem lehet kongruens 5 (mod 6), és a sorozat segítségével bebizonyítható, hogy végtelen sok olyan prím létezik, ami kongruens 7 (mod 12).

A Sylvester-számok faktorizációjával kapcsolatban számos kérdés áll még nyitva. Nem ismert például, hogy minden tag négyzetmentes-e, bár az összes ismert tag az.

Ahogy  írja, könnyen meghatározható, hogy adott p melyik Sylvester-számnak osztója (ha osztója bármelyiknek): egyszerűen modulo p kell számítani a Sylvester-sorozat rekurrenciáját, amíg olyan számhoz nem érünk, ami kongruens 0-vel (mod p), vagy ismétlődő modulushoz. Ezzel a technikával az első 3 millió prímszám közül 1166 vagy 1167 prímosztóját találta meg a Sylvester-számoknak, melyek közül egyiknek a négyzete sem volt osztója Sylvester-számnak.
A Sylvester-számokat osztó prímszámok sűrűsége nulla az összes prímszám között: valóban, az x-nél kisebb ilyen prímek száma .

A következő táblázat a Sylvester-számok prímtényezős felbontását mutatja be (kivétel az első 4 tag, amik prímek):

A konvencióknak megfelelően Pn és Cn n számjegy hosszúságú prímszámokat és összetett számokat jelöl.

Alkalmazásai 
 a Sylvester-sorozat tulajdonságait használják fel arra, hogy nagy számú olyan Szaszaki-féle Einstein-sokaságot definiáljanak, melyek differenciális topológiája megegyezik a páratlan dimenziójú gömbökével vagy egzotikus gömbökével. Megmutatják, hogy a 2n − 1 dimenziós topologikus gömb különböző Szaszaki-féle Einstein-metrikája legalább arányos az sn-nel, így n-re nézve dupla exponenciálisan nő.

Ahogy  is lejegyezte,  és  a Sylvester-sorozatból vett értékekkel konstruált alsó korlátos példákat az online ládapakolási algoritmusokhoz.  hasonlóan használta fel a sorozatot egy kétdimenziós szabási feladat-algoritmus teljesítményének alsó korlátjának beállítására.

A Znám-probléma olyan számhalmazokkal foglalkozik, melyek közül bármelyik szám osztója az összes többi szám szorzata plusz 1-nek, de egyik szám sem azonos vele (tehát valódi osztója). Az utóbbi követelmény hiányában a Sylvester-sorozat értékei megoldásait adnák a problémának; a követelménnyel együtt más megoldásai vannak, melyek a Sylvester-sorozatéhoz hasonló rekurziókból származnak. A Znám-probléma megoldásainak a felületi szingularitások osztályozásában (Brenton and Hill 1988) és a nemdeterminisztikus véges állapotú automaták elméletében vannak alkalmazásai.

 leírja a k taggal való, egyhez legközelebbi közelítések egy alkalmazását a tökéletes számok osztószámának alsó korlátjának meghatározásában;  ugyanezt a tulajdonságot használja bizonyos csoportok méretére vonatkozó alsó korlát meghatározására.

Kapcsolódó szócikkek 
 Cahen-állandó
 Elsődleges áltökéletes számok
 Eukleidész–Mullin-sorozat

Jegyzetek

Irodalom 

 
 

 
 
 
 
 
 
 
 

Jones, Rafe (2006). "The density of prime divisors in the arithmetic dynamics of quadratic polynomials" arXiv:math.NT/0612415

További információk 
 Irrationality of Quadratic Sums, from K. S. Brown's MathPages.
 

Egyiptomi törtek
Nevezetes számsorozatok
Végtelen sorok
Számelmélet
A számelmélet területén a Sylvester-sorozat vagy Sylvester-féle sorozat olyan egész számokat tartalmazó sorozat , melynek minden tagja az előző tagok összeszorzásával éshozzáadásával képezhető . A sorozat első néhány tagja : 2 , , , . A Sylvester-sorozatot James Joseph Sylvester brit matematikusról nevezték el , akiban elsőként tanulmányozta . A sorozat tagjai dupla exponenciális sebességgel nőnek , reciprokainak egységtört-sorösszege pedig gyorsabban tarthez , mint bármely más egységtört-sorozat . A rekurzív definíció lehetővé teszi , hogy a sorozat tagjait a hasonló nagyságrendű számoknál gyorsabban lehessen prímtényezőkre bontani , de a sorozat gyors növekedése miatt így is csak az első néhány tagnak ismert a pontos felbontása . A sorozat felhasználási módjai között van azvéges egyiptomi tört-felbontásainak konstruálása , a Szaszaki–Einstein-sokaságok ( , ) tagjai és az online algoritmusok keményebb darabjai . Formális definíciók A Sylvester-sorozat formális meghatározása : Az üres szorzat értéke megegyezés szerint ezért s0 = Egy másik rekurzív definíció szerint : ahol s0 = Könnyen megmutatható a két definíció egyenértékűsége . Zárt alak , aszimptotikus viselkedés A Sylvester-számok n függvényében dupla exponenciálisan nőnek . Megmutatható , hogy az E számra , ami körülbelül264084735305302 . A képlet hatásában a következő algoritmussal egyezik meg : s0 az E2-höz legközelebb álló egész szám ; s1 az E4-hez legközelebb álló egész szám ; s2 az E8-hoz legközelebb álló egész szám ; bármely sn-re , vedd E2-t , emeld négyzetre n-szer és vedd a hozzá legközelebbi egész számot . Ez akkor lehetne praktikus algoritmus , ha lenne más módja E meghatározásának , mint az sn kiszámolása és egymás utáni négyzetgyökvonások . A Sylvester-sorozat dupla exponenciális növekedése nem meglepő , összehasonlítva őket az Fn Fermat-számok sorozatával ; a Fermat-számokat általában egy dupla exponenciális képlettel adják meg – – , de valójában a Sylvester-sorozathoz hasonló módon is megadhatók lennének : Egyiptomi törtekkel való kapcsolatai A Sylvester-sorozat reciprokai által megadott egységtörtek végtelen sora a következő : A sor részösszegeinek egyszerű alakja : Ez igazolható indukcióval , vagy közvetlen módon , belátva hogy a rekurzióból következik : tehát az összegzést teleszkóposan elvégezve : Mivel a részösszegek ezen ( sj-2) /( sj-1 ) sorozata egyhez konvergál , a teljes sor azszám végtelen egyiptomi tört-reprezentációját adja : Azbármilyen hosszú egyiptomitört-megfeleltetése megkapható a sorozat „ levágásával” , majd az utolsó nevezőbőllevonásával : A végtelen sorozat első k tagjának összege adja a legközelebbi lehetséges alsó becslésétnek az összes k-tagú egyiptomi törtes sorozat között . Például az első négy tag összege1806 , ezért bármely , az1806,1 ) nyílt intervallumban lévő egyiptomitört-megfeleltetés legalábbelemet igényel . A Sylvester-sorozat úgy is felfogható , mint egy egyiptomi törteket előállító mohó algoritmus , ami minden lépésben kiválasztja a lehető legkisebb nevezőt , amitől a sor részösszege még egy alatt marad . Más megközelítésben a sorozat első tagjától tekinthető az ½ páratlan mohó felbontásának . Egyediség és racionális összegű gyorsan növő sorok Amint azt Sylvester maga is megjegyezte , a Sylvester-sorozat egyedinek tűnik abban a tekintetben , hogy ilyen gyorsan növekvő értékek mellett a reciprokok összege racionális számhoz konvergál . A sorozat példát nyújt arra , hogy önmagában a dupla exponenciális növekedés nem elégséges feltétele az irracionalitás-sorozatságnak . Precízebben , -ból következik , hogy ha egy sorozat elég gyorsan nő ahhoz , hogy és az sorozat egy A racionális számhoz konvergál , akkor egy adott számot elérve minden n számra a sorozatot ugyanaz az rekurrencia-szabály kell , hogy meghatározza , mint a Sylvester-sorozatot. sejtése szerint az ilyen típusú eredményekben a sorozat növekedését korlátozó egyenlőtlenség lecserélhető a következő gyengébb feltételre : vizsgálta a sejtés megoldásának előrehaladását ; lásd még \ . Oszthatóság és prímfelbontások Ha i < j , a definícióból következik , hogy sj ≡( mod si ) . Ezért a Sylvester-sorozat bármely két tagja relatív prím . A sorozat annak bizonyítására is alkalmas , hogy végtelen sok prímszám létezik , hiszen bármely prímszám a sorozat legfeljebb egy tagjának lehet osztója . Ezen túl , a sorozat tagjainak egyetlen prímtényezője sem lehet kongruens( mod és a sorozat segítségével bebizonyítható , hogy végtelen sok olyan prím létezik , ami kongruens( mod A Sylvester-számok faktorizációjával kapcsolatban számos kérdés áll még nyitva . Nem ismert például , hogy minden tag négyzetmentes-e , bár az összes ismert tag az . Ahogy írja , könnyen meghatározható , hogy adott p melyik Sylvester-számnak osztója ( ha osztója bármelyiknek ) : egyszerűen modulo p kell számítani a Sylvester-sorozat rekurrenciáját , amíg olyan számhoz nem érünk , ami kongruensvel ( mod p ) , vagy ismétlődő modulushoz . Ezzel a technikával az elsőmillió prímszám közülvagyprímosztóját találta meg a Sylvester-számoknak , melyek közül egyiknek a négyzete sem volt osztója Sylvester-számnak . A Sylvester-számokat osztó prímszámok sűrűsége nulla az összes prímszám között : valóban , az x-nél kisebb ilyen prímek száma \ . A következő táblázat a Sylvester-számok prímtényezős felbontását mutatja be ( kivétel az elsőtag , amik prímek ) : A konvencióknak megfelelően Pn és Cn n számjegy hosszúságú prímszámokat és összetett számokat jelöl . Alkalmazásai a Sylvester-sorozat tulajdonságait használják fel arra , hogy nagy számú olyan Szaszaki-féle Einstein-sokaságot definiáljanak , melyek differenciális topológiája megegyezik a páratlan dimenziójú gömbökével vagy egzotikus gömbökével . Megmutatják , hogy a −dimenziós topologikus gömb különböző Szaszaki-féle Einstein-metrikája legalább arányos az sn-nel , így n-re nézve dupla exponenciálisan nő . Ahogy is lejegyezte , és a Sylvester-sorozatból vett értékekkel konstruált alsó korlátos példákat az online ládapakolási algoritmusokhoz . hasonlóan használta fel a sorozatot egy kétdimenziós szabási feladat-algoritmus teljesítményének alsó korlátjának beállítására . A Znám-probléma olyan számhalmazokkal foglalkozik , melyek közül bármelyik szám osztója az összes többi szám szorzata plusznek , de egyik szám sem azonos vele ( tehát valódi osztója ) . Az utóbbi követelmény hiányában a Sylvester-sorozat értékei megoldásait adnák a problémának ; a követelménnyel együtt más megoldásai vannak , melyek a Sylvester-sorozatéhoz hasonló rekurziókból származnak . A Znám-probléma megoldásainak a felületi szingularitások osztályozásában ( Brenton and Hillés a nemdeterminisztikus véges állapotú automaták elméletében vannak alkalmazásai. leírja a k taggal való , egyhez legközelebbi közelítések egy alkalmazását a tökéletes számok osztószámának alsó korlátjának meghatározásában ; ugyanezt a tulajdonságot használja bizonyos csoportok méretére vonatkozó alsó korlát meghatározására . Kapcsolódó szócikkek Cahen-állandó Elsődleges áltökéletes számok Eukleidész–Mullin-sorozat Jegyzetek Irodalom Jones , Rafe " The density of prime divisors in the arithmetic dynamics of quadratic polynomials " arXiv: math.NT/0612415 További információk Irrationality of Quadratic Sums , from K. S. Brown's MathPages . Egyiptomi törtek Nevezetes számsorozatok Végtelen sorok Számelmélet