Sylvester-sorozat
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Sylvester-square.svg/300px-Sylvester-square.svg.png)
A számelmélet területén a Sylvester-sorozat (vagy Sylvester-féle sorozat) olyan egész számokat tartalmazó sorozat, melynek első tagja a 2, és minden további tag az előző tagok szorzatánál 1-gyel nagyobb szám. Így az első néhány tagja:
- 2, 3, 7, 43, 1807, 3263443, 10650056950807, 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 azt. A sorozat tagjai dupla exponenciális sebességgel nőnek, a reciprokok sorösszege pedig gyorsabban tart 1-hez, mint bármely más egységtört-sorozat. A rekurzív definíció lehetővé teszi a sorozat tagjainak gyorsabb prímtényezőkre bontását a velük azonos nagyságrendű egész számokhoz képest, de a sorozat rendkívül gyors növekedése miatt így is csak az első néhány tagnak ismert a pontos felbontása. A sorozat felhasználható az 1 véges egyiptomitört-felbontásaihoz, a Szaszaki–Einstein-sokaságok ((wd), (wd)) konstruálásához és egyes bonyolultabb online algoritmusokban (olyan algoritmusok, amelyek a bemenetet nem egyszerre kapják meg, hanem több részben, a feldolgozási folyamat közben).
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 a sorozat kezdőértéke.
Egy másik rekurzív definíció:
- és (minden -ra)
Könnyen megmutatható a két definíció egyenértékűsége (teljes indukcióval).
Zárt alak, aszimptotikus viselkedés
A Sylvester-számok n függvényében dupla exponenciálisan nőnek. Megmutatható, hogy
egy E számra, ami körülbelül 1,264084735305302.[1] Ez azt jelenti, hogy s0 az E2-hez 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 stb.
Az előbbi képlet hatásában a következő algoritmussal egyezik meg: bármely sn-re, vedd E2-et, emeld négyzetre n-szer, majd vedd a hozzá legközelebbi egész számot. Ez viszont csak akkor lehetne praktikus algoritmus, ha az sn kiszámolásán, majd egymás utáni négyzetgyökvonásokon kívül lenne más módja is E meghatározásának.
A Sylvester-sorozat dupla exponenciális növekedése nem meglepő, ha összehasonlítjuk az Fermat-számok sorozatával, hiszen a Fermat-számok az előbbi megszokott képlet mellett a Sylvester-sorozathoz hasonló módon is megadhatóak:
Egyiptomi törtekkel való kapcsolatai
A Sylvester-sorozat reciprokai által kapott egységtörtek végtelen sora a következő:
A sor részösszegeinek egyszerű alakja:
ami igazolható indukcióval, vagy akár közvetlen módon – belátva, hogy a rekurzióból következik az
összefüggés, amivel teleszkopikus összegzést végezve:
Mivel a részösszegek ezen sorozata 1-hez konvergál, ezért a teljes sor az 1-nek végtelen egyiptomitö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ó tört nevezőjéből 1 levonásával, például:
Ez általánosan így néz ki egy tetszőleges k index esetén: .
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 (1805/1806, 1) 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 1 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 Sylvester-sorozat példát nyújt arra, hogy önmagában a dupla exponenciális növekedés nem elégséges feltétele a sorozat irracionális voltának.[3]
Ha egy sorozat elég gyorsan nő ahhoz, hogy
és a sorozat egy A racionális számhoz konvergál, akkor egy bizonyos küszöbindextől kezdődően minden n indexre az sorozatot ugyanazon
rekurrencia-szabály kell meghatározza, mint a Sylvester-sorozatot (Badea 1993).
(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ások
Ha i < j, a definícióból következik, hogy . Ezért a Sylvester-sorozat bármely két tagja relatív prím. Továbbá a sorozat tagjainak egyetlen prímtényezője sem lehet kongruens 5-tel modulo 6. A sorozat segítségével bebizonyítható, hogy végtelen sok prímszám létezik (hiszen bármely prímszám a sorozat legfeljebb egy tagjának lehet osztója), sőt, sorozat segítségével az is bebizonyítható, hogy végtelen sok olyan prím létezik, ami kongruens 7-tel modulo 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.
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] Konvenció szerint Pn és Cn bizonyos n számjegyű prímszámokat, illetve összetett számokat jelölnek.
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 |
Alkalmazásai
(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ócikkek
- Cahen-állandó
- Elsődleges áltökéletes számok
- Eukleidész–Mullin-sorozat
Jegyzetek
- ↑ (Graham, Knuth & Patashnik 1989) feladatként határozta ezt meg, lásd még (Golomb 1963).
- ↑ 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).
- ↑ Guy,2004
- ↑ Guy,Nowakowski(1975)
- ↑ Jones(2006)
- ↑ Odoni(1985)
- ↑ 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.
- ↑ 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.
- ↑ Domaratzki,Ellul,Shallit,Wang(2005)
Irodalom
- Badea, Catalin (1993). „A theorem on irrationality of infinite series and applications”. Acta Arithmetica 63, 313–323. o.
- Badea, Catalin: On some criteria for irrationality for series of positive rationals: a survey, 1995. [2008. szeptember 11-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 21.)
- (2005) „Einstein metrics on spheres”. Annals of Mathematics 162 (1), 557–580. o. DOI:10.4007/annals.2005.162.557.
- (1988) „On the Diophantine equation 1=Σ1/ni + 1/Πni and a class of homologically trivial complex surface singularities”. Pacific Journal of Mathematics 133 (1), 41–67. o. DOI:10.2140/pjm.1988.133.41.
- Brown, D. J. (1979). „A lower bound for on-line one-dimensional bin packing algorithms”, Kiadó: Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign.
- Curtiss, D. R. (1922). „On Kellogg's diophantine problem”. American Mathematical Monthly 29 (10), 380–387. o. DOI:10.2307/2299023.
- (2005) „Non-uniqueness and radius of cyclic unary NFAs”. International Journal of Foundations of Computer Science 16 (5), 883–896. o. DOI:10.1142/S0129054105003352.
- Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève (1980)
- (1995) „On-line bin packing — A restricted survey”. Mathematical Methods of Operations Research 42 (1), 25. o. DOI:10.1007/BF01415672.
- (1963) „On certain nonlinear recurring sequences”. American Mathematical Monthly 70 (4), 403–405. o. DOI:10.2307/2311857.
- Concrete Mathematics, 2nd, Addison-Wesley (1989). ISBN 0-201-55802-5
- Guy, Richard K.. Unsolved Problems in Number Theory, 3rd, Springer-Verlag, 346. o. (2004). ISBN 0-387-20860-7
- (1975) „Discovering primes with Euclid”. Delta (Waukesha) 5 (2), 49–63. o.
- Jones, Rafe (2006). "The density of prime divisors in the arithmetic dynamics of quadratic polynomials" arXiv:math.NT/0612415
- Liang, Frank M. (1980). „A lower bound for on-line bin packing”. Information Processing Letters 10 (2), 76–79. o. DOI:10.1016/S0020-0190(80)90077-0.
- Miller, G. A. (1919). „Groups possessing a small number of sets of conjugate operators”. Transactions of the American Mathematical Society 20 (3), 260–270. o. DOI:10.2307/1988867.
- Odoni, R. W. K. (1985). „On the prime divisors of the sequence wn+1 =1+w1⋯wn”. J. Lond. Math. Soc., II. Ser. 32, 1-11. o.
- Rosenman, Martin (1933). „Problem 3536”. American Mathematical Monthly 40 (3), 180–181. o. DOI:10.2307/2301036.
- Salzer, H. E. (1947). „The approximation of numbers as sums of reciprocals”. American Mathematical Monthly 54 (3), 135–142. o. DOI:10.2307/2305906.
- (2005) „The two-dimensional cutting stock problem revisited”. Mathematical Programming 102 (3), 519–530. o. DOI:10.1007/s10107-004-0548-1.
- Soundararajan, K. (2005). „Approximating 1 from below using n Egyptian fractions”.
- Sylvester, J. J. (1880). „On a point in the theory of vulgar fractions”. American Journal of Mathematics 3 (4), 332–335. o. DOI:10.2307/2369261.
- Vardi, Ilan. Computational Recreations in Mathematica. Addison-Wesley, 82–89. o. (1991). ISBN 0-201-52989-0
További információk
- Irrationality of Quadratic Sums, from K. S. Brown's MathPages.
- Weisstein, Eric W.: Sylvester's Sequence (angol nyelven). Wolfram MathWorld