Főmenü megnyitása

Sylvester-sorozat

egész számokból álló sorozat, melynek minden tagja az előző tagok produktuma plusz 1
Az 1/2 + 1/3 + 1/7 + 1/43 + ... összeg 1-hez való konvergenciájának ábrázolása. Minden sorban k db négyzet van, 1/k oldalhosszúsággal, melyek területösszege 1/k, az összes négyzet pedig pontosan lefed egy nagyobb, 1 területű négyzetet. Az 1/1807 vagy kisebb oldalhosszúságú négyzetek nem szerepelnek az ábrán

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, 3 263 443, 10 650 056 950 807, 113423713055421844361000443 (A000058 sorozat az OEIS-ben).

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 SzaszakiEinstein-sokaságok ((wd), (wd)) tagjai és az online algoritmusok keményebb darabjai.

Formális definíciókSzerkesztés

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ésSzerkeszté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.[1] 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ó kapcsolataiSzerkesztés

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.[2] 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(wd), 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ő sorokSzerkesztés

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.[3]

Precízebben, (Badea 1993)-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.

(Erdős & Graham 1980) 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:

 

(Badea 1995) vizsgálta a sejtés megoldásának előrehaladását; lásd még (Brown 1979).

Oszthatóság és prímfelbontásokSzerkesztés

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).[4]

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 (Vardi 1991) í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:[5] valóban, az x-nél kisebb ilyen prímek száma  .[6]

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):[7]

n sn prímtényezői
4 13 × 139
5 3263443, ami prím
6 547 × 607 × 1033 × 31051
7 29881 × 67003 × 9119521 × 6212157481
8 5295435634831 × 31401519357481261 × 77366930214021991992277
9 181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851
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 × 54062008753544850522999875710411 × C6618
16 128551 × C13335
17 635263 × 1286773 × 21269959 × C26661
18 50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19 775608719589345260583891023073879169 × C106685
20 352867 × 6210298470888313 × C213419
21 387347773 × 1620516511 × C426863
22 91798039513 × C853750

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

AlkalmazásaiSzerkesztés

(Boyer, Galicki & Kollár 2005) 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 (Galambos & Woeginger 1995) is lejegyezte, (Brown 1979) és (Liang 1980) a Sylvester-sorozatból vett értékekkel konstruált alsó korlátos példákat az online ládapakolási algoritmusokhoz. (Seiden & Woeginger 2005) 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.[8]

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.[9]

D. R. Curtiss (1922) 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; (Miller 1919) ugyanezt a tulajdonságot használja bizonyos csoportok méretére vonatkozó alsó korlát meghatározására.

Kapcsolódó szócikkekSzerkesztés

JegyzetekSzerkesztés

  1. (Graham, Knuth & Patashnik 1989) feladatként határozta ezt meg, lásd még (Golomb 1963).
  2. Ezt az állítást általában (Curtiss 1922)-nek tulajdonítják, de (Miller 1919) ugyanezt a kijelentést teszi egy korábbi írásában. Lásd még (Rosenman & Underwood 1933), (Salzer 1947) és (Soundararajan 2005).
  3. Guy,2004
  4. Guy,Nowakowski(1975)
  5. Jones(2006)
  6. Odoni(1985)
  7. Az sn Sylvester-számok azon p prímtényezőit, ahol p < 5·107 és n ≤ 200, Vardi listázza. Ken Takusagawa listázza a felbontásokat egészen s9-ig, illetve s10-ig. A többi prímtényezős felbontást a Jens Kruse Andersen által fenntartott a list of factorizations of Sylvester's sequence oldal tartja számon.
  8. Munkájukban Seiden és Woeginger végig „Salzer sorozata”-ként hivatkoznak a Sylvester-sorozatra, (Salzer 1947) legjobb approximációra vonatkozó munkája nyomán.
  9. Domaratzki,Ellul,Shallit,Wang(2005)

IrodalomSzerkesztés

További információkSzerkesztés