Prímek számtani sorozata
A számelmélet területén prímszámokból álló számtani sorozat vagy röviden prímek számtani sorozata alatt olyan, legalább három prímszámból álló szekvenciát értünk, melyek egymást követő elemei egy számtani sorozatnak. Például a 3, 7, 11 prímszámok sorozata, ami az képlettel határozható meg értékekre. A Green–Tao-tétel szerint tetszőlegesen hosszú prímszámokból álló számtani sorozat létezik. Néha a prímszámok számtani sorozata alatt olyan prímszámokat értenek, melyek egyébként összetett számokat tartalmazó számtani sorozat részét képezik. Például tekinthetjük az alakú prímszámokat, ahol a és b relatív prímek; a Dirichlet-tétel szerint az ilyen sorozatok végtelen sok prímszámot tartalmaznak, valamint végtelen sok összetett számot is. A k ≥ 3 egész számokra, egy AP-k (vagy PAP-k, azaz prime arithmetic progression of length k) olyan sorozat, ami k prímszámot tartalmaz egy számtani sorozat részeként. Az AP-k felírható a·n + b alakú k db prímszámként, fix a (a sorozat különbsége) és b egészekre, k egymást követő n egész értékre. Az AP-k-t általában n = 0 – k − 1 közötti értékekkel adják meg. Ez úgy érhető el, ha b az első prím a számtani sorozatban.
Jellemzői
Prímek bármely számtani sorozata véges hosszúságú. 2004-ben Ben Green és Terence Tao eldöntöttek egy régi sejtést, amikor igazolták a Green–Tao-tételt: a prímek között tetszőleges hosszúságú számtani sorozatok léteznek.[1] A tételből azonnal következik, hogy bármely k számhoz végtelen sok AP-k létezik. Ha egy AP-k nem a k prímszámmal kezdődik, akkor a sorozat különbsége a k# = 2·3·5·...·j primoriális többszöröse, ahol j a legnagyobb prím ≤ k.
- Bizonyítás: Legyen AP-k a·n + b k egymást követő n értékre. Ha a p prím nem osztója a-nak, akkor a moduláris aritmetika szerint p a számtani sorozat minden p-edik elemét osztani fogja.[2] Ha az AP k egymást követő értéke prímszám, akkor az a-nak oszthatónak kell lennie az összes p ≤ k prímszámmal.
Az előbbiekből az is következik, hogy az a különbségű AP nem tartalmazhat több egymást követő prímet, mint a legkisebb, a-t nem osztó prím számértéke. Ha k prímszám, akkor az AP-k kezdődhet k-vel, és a sorozat különbsége elég, ha (k−1)# többszöröse k# helyett.[3] Megfigyelhető az AP-3 a {3, 5, 7} prímekkel és 2# = 2 különbséggel, vagy az AP-5 {5, 11, 17, 23, 29} és 4# = 6 különbséggel. A sejtések szerint ilyen példák minden k prímszámra hozhatók. Jelenleg (2016) a legnagyobb prím, amire ezt sikerült igazolni a k = 19, a következő AP-19-re, amit Wojciech Iżykowski talált meg 2013-ban:
- 19 + 4244193265542951705·17#·n, ahol n = 0 – 18.[4]
Széles körben igaznak vélt sejtésekből, mint a Dickson-sejtés és az első Hardy–Littlewood-sejtés (prím n-esekre vonatkozó sejtés) következik, hogy ha p > 2 a legkisebb prímszám, ami nem osztja a-t, akkor végtelen sok a különbségű AP-(p−1) létezik. Például 5 a legkisebb prím, ami nem osztója a 6-nak, ezért arra számítunk, hogy végtelen sok 6 különbségű AP-4-et találunk (szexi prím-négyesek). Az a = 2, p = 3 kiadja az ikerprímsejtést, az "AP-2" 2 prímre (b, b + 2).
A legnagyobb ismert prímek számtani sorozatban
A q prímszám esetén, q# jelölje a 2·3·5·7·...·q primoriálist. Jelenleg (2016. március) a leghosszabb ismert AP-k közül a legnagyobb egy AP-26, amit 2015. február 19-én talált Bryan Little[5] egy AMD R9 290 GPU-n módosított AP26 szoftverrel. Ez a negyedik ismert AP-26:
- 161004359399459161 + 47715109·23#·n, ahol n = 0 – 25. (23# = 223092870)
A harmadik ismert AP-26-ot Bryan Little találta 2014. február 23-án:[5]
- 136926916457315893 + 44121555·23#·n, ahol n = 0 – 25. (23# = 223092870)
A második ismert AP-26-ot James Fry találta meg 2012. március 16-án:[5]
- 3486107472997423 + 1666981·23#·n, ahol n = 0 – 25. (23# = 223092870)
Az első ismert AP-26-ot 2010. április 12-én Benoãt Perichon találta egy PlayStation 3-mal, a Jaroslaw Wroblewski és Geoff Reynolds által írt szoftverrel, amit Bryan Little ültetett át a PlayStation 3-ra, egy elosztott PrimeGrid projekt keretében:[5]
- 43142746595714191 + 23681770·23#·n, ahol n = 0 – 25. (23# = 223092870) (A204189 sorozat az OEIS-ben)
Mire az első AP-26-ot megtalálták, a keresést a PrimeGrid 131 436 182 szegmensre osztotta szét,[6] a munkát pedig világszerte különböző 32/64 bites CPU-k, Nvidia CUDA GPU-k és Cell mikroprocesszorok végezték. Korábban a rekord egy 2008. május 17-én Raanan Chermoni és Jaroslaw Wroblewski által megtalált AP-25 volt:[5]
- 6171054912832631 + 366384·23#·n, ahol n = 0 – 24. (23# = 223092870)
Az AP-25 keresést akkora szegmensekre szabdalták, hogy egy szegmens végigszámolására egy Athlon 64-nek kb. 3 percre volt szüksége, Wroblewski szerint „Raanan kevesebb mint 10 000 000 ilyen szegmensen haladt végig”[7] (ez 57 CPU-évet vett volna igénybe Athlon 64-en). A korábbi rekord egy Jaroslaw Wroblewski által 2007. január 18-án egyedül megtalált AP-24 volt:
- 468395662504823 + 205619·23#·n, ahol n = 0 – 23.
Ehhez Wroblewski saját bevallása szerint összesen 75 számítógépet használt: 15 64 bites Athlont, 15 dual core 64 bites Pentium D 805-öst, 30 32 bites Athlon 2500-at és 15 Duron 900-at.[8] A következő táblázat megmutatja a legnagyobb ismert AP-k-kat a felfedezési évükkel és a záróprím számjegyeinek számával. Vegyük észre, hogy a legnagyobb ismert AP-k lehet egy AP-(k+1) vége is. Egyes csúcstartók először kiszámolnak fix p-vel nagyszámú c·p#+1 alakú prímszámot, majd a prímet adó c értékek között keresnek számtani sorozatokat. Ez látható egyes rekordok formájából is. A kifejezés könnyen átírható a·n + b alakra.
| k | Prímek n = 0 – k−1 | Számjegyek | Év | Felfedező |
|---|---|---|---|---|
| 1 | 257885161 + 422·n − 1 | 17425170 | 2013 | GIMPS, Curtis Cooper |
| 2 | 243112609 + (257885161 − 243112609)·n − 1 | 12978189 | 2013 | GIMPS, Edson Smith, Curtis Cooper |
| 3 | (483590093385 + 1367824406910·n)·21290000 − 1 | 388342 | 2015 | David Broadhurst, Ernst Fluttert, Randall Scalise, PrimeGrid |
| 4 | 1631979959·225000 + (164196977·280000 − 1631979959·225000)·n − 1 | 24092 | 2010 | David Broadhurst |
| 5 | (43728051 + 18797279·n)·16267# - 1 | 7026 | 2015 | Serge Batalov |
| 6 | (234043271 + 481789017·(n + 1))·7001# + 1 | 3019 | 2012 | Ken Davis |
| 7 | (234043271 + 481789017·n)·7001# + 1 | 3019 | 2012 | Ken Davis |
| 8 | (452558752 + 359463429·n)·2459# + 1 | 1057 | 2009 | Ken Davis |
| 9 | (65502205462 + 6317280828·n)·2371# + 1 | 1014 | 2012 | Ken Davis, Paul Underwood |
| 10 | (3186700865 + 61959394·(n + 1))·653# + 1 | 283 | 2010 | Ken Davis |
| 11 | (3186700865 + 61959394·n)·653# + 1 | 283 | 2010 | Ken Davis |
| 12 | (1366899295 + 54290654·n)·401# + 1 | 173 | 2006 | Jeff Anderson-Lee |
| 13 | (1296982250 + 14976848·n)·191#+1 | 85 | 2010 | Mike Oakes |
| 14 | (145978014 + 25313115·n)·157# + 1 | 71 | 2009 | Mike Oakes |
| 15 | (237375311 + 118560155·n)·109# + 1 | 54 | 2009 | Mike Oakes |
| 16 | 442604220336549402080078796974991691613909 + 103#·(n + 1) | 42 | 2014 | Jaroslaw Wroblewski |
| 17 | 442604220336549402080078796974991691613909 + 103#·n | 42 | 2014 | Jaroslaw Wroblewski |
| 18 | 1029+999 + 1806448944300798320195·19#·(n − 1) | 30 | 2014 | Jaroslaw Wroblewski |
| 19 | 1029+999 + 1806448944300798320195·19#·(n − 2) | 30 | 2014 | Jaroslaw Wroblewski |
| 20 | 3533531731191494525351461 + 61#·n | 25 | 2014 | Jaroslaw Wroblewski |
| 21 | 5547796991585989797641 + 29#·n | 22 | 2014 | Jaroslaw Wroblewski |
| 22 | 22231637631603420833 + 8·41#·(n + 1) | 20 | 2014 | Jaroslaw Wroblewski |
| 23 | 22231637631603420833 + 8·41#·n | 20 | 2014 | Jaroslaw Wroblewski |
| 24 | 161004359399459161 + 47715109·23#·(n + 2) | 18 | 2015 | Bryan Little |
| 25 | 161004359399459161 + 47715109·23#·(n + 1) | 18 | 2015 | Bryan Little |
| 26 | 161004359399459161 + 47715109·23#·n | 18 | 2015 | Bryan Little |
Egymást követő prímekből álló számtani sorozat
Az egymást követő prímekből álló számtani sorozat (Consecutive primes in arithmetic progression, CPAP) legalább három egymást követő prímet jelent, melyek egy számtani sorozat egymást követő tagjai. Az AP-k-tól eltérően a sorozat tagjai között lévő valamennyi számnak összetettnek kell lennie. Például az AP-3 {3, 7, 11} nem CPAP, mert a közéjük eső 5 prímszám. Egy k ≥ 3 egész számhoz tartozó CPAP-k k db egymást követő prímszámot jelent, melyek egy számtani sorozat egymást követő elemei. Sejtések szerint létezik tetszőlegesen hosszú CPAP – ebből az következik, hogy végtelen sok CPAP-k létezik bármely k-ra. A CPAP-3 középső prímszámját kiegyensúlyozott prímnek is nevezik. A legnagyobb ismert ilyen (2014) prím 10 546 számjeggyel írható le. Az első ismert CPAP-10-et 1998-ban találta Manfred Toplic a CP10 elosztott számítási projektben, amit Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony és Paul Zimmermann szerveztek.[9] Ez a CPAP-10 a lehetséges legkisebb különbségű volt: 7# = 210. A másik ismert CPAP-10-et ugyanez a csapat találta meg 2009-ben. Ha létezik CPAP-11, a sorozat különbségének 11# = 2310-nek vagy ennek többszörösének kell lennie. A 11 prímszám első és utolsó tagja közti különbség tehát 23 100 (vagy ennek többszöröse). Az a követelmény, hogy a 11 prímszám között legalább 23 090 összetett szám legyen, rendkívüli módon megnehezíti egy CPAP-11 megtalálását. Dubner és Zimmermann becslése szerint legalább 1012-szer olyan nehézzé, mint amilyen a CPAP-10 megtalálása volt.[10]
A legnagyobb ismert egymást követő prímekből álló számtani sorozatok (CPAP)
A következő táblázat megmutatja a legnagyobb ismert, egymást követő k prímszámból álló számtani sorozatokat, k = 3–10 esetekre.
| k | Prímek n = 0 – k−1 | Számjegyek | Év | Felfedező |
|---|---|---|---|---|
| 3 | 1213266377 · 235000 − 1 + 2430n | 10546 | 2014 | David Broadhurst |
| 4 | 62037039993 · 7001# + 7811555723 + 30n | 3021 | 2013 | David Broadhurst |
| 5 | 406463527990 · 2801# + 1633050283 + 30n | 1209 | 2013 | David Broadhurst |
| 6 | 44770344615 · 859# + 1204600427 + 30n | 370 | 2003 | Jens Kruse Andersen, Jim Fougeron |
| 7 | 4785544287883 · 613# + x253 + 210n | 266 | 2007 | Jens Kruse Andersen |
| 8 | 10097274767216 · 250# + x99 + 210n | 112 | 2003 | Jens Kruse Andersen |
| 9 | 73577019188277 · 199#·227·229 + x87 + 210n | 101 | 2005 | Hans Rosenthal, Jens Kruse Andersen |
| 10 | 1180477472752474 · 193# + x77 + 210n | 93 | 2008 | Manfred Toplic, CP10 project |
xd egy d-számjegyű szám, amire azért volt szükség, hogy a prímszámok közötti összetett számoknak legyen megfelelő mennyiségű kis prímtényezője.
x77 = 54538241683887582 668189703590110659057865934764 604873840781923513421103495579
x87 = 279872509634587186332039135 414046330728180994209092523040 703520843811319320930380677867
x99 = 158794709 618074229409987416174386945728 371523590452459863667791687440 944143462160821328735143564091
x253 = 1617599298905 320471304802538356587398499979 836255156671030473751281181199 911312259550734373874520536148 519300924327947507674746679858 816780182478724431966587843672 408773388445788142740274329621 811879827349575247851843514012 399313201211101277175684636727
Kapcsolódó szócikkek
Jegyzetek
- ↑ Green, Ben & Tao, Terence (2008), "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics 167 (2): 481–547, DOI 10.4007/annals.2008.167.481
- ↑ lásd H.J. Weber, Cor.10 in ``Exceptional Prime Number Twins, Triplets and Multiplets," arXiv:1102.3075[math.NT]. Lásd még Theor.2.3 in ``Regularities of Twin, Triplet and Multiplet Prime Numbers," arXiv:1103.0447[math.NT],Global J.P.A.Math 8(2012), in press.
- ↑ Lásd H. J. Weber, ``Less Regular Exceptional and Repeating Prime Number Multiplets," arXiv:1105.4092[math.NT], Sect.3.
- ↑ http://primerecords.dk/aprecords.htm
- ↑ 5,0 5,1 5,2 5,3 5,4 5,5 Jens Kruse Andersen, Primes in Arithmetic Progression Records. Retrieved 2015-12-05.
- ↑ John, AP26 Forum. Retrieved 2013-10-20.
- ↑ Wroblewski, Jaroslaw (2008-05-17), "AP25", primenumbers mailing list
- ↑ Wroblewski, Jaroslaw (2007-01-18), "AP24", primeform mailing list
- ↑ H. Dubner, T. Forbes, N. Lygeros, M. Mizony, H. Nelson, P. Zimmermann, Ten consecutive primes in arithmetic progression, Mathematics of Computation 71 (2002), 1323–1328.
- ↑ Manfred Toplic, The nine and ten primes project. Retrieved on 2007-06-17.
- ↑ Jens Kruse Andersen, The Largest Known CPAP's. Retrieved on 2014-06-13.
Irodalom
- Chris Caldwell, The Prime Glossary: arithmetic sequence, The Top Twenty: Arithmetic Progressions of Primes and The Top Twenty: Consecutive Primes in Arithmetic Progression, all from the Prime Pages.
- Weisstein, Eric W.: Prime Arithmetic Progression (angol nyelven). Wolfram MathWorld
- Jaroslaw Wroblewski, How to search for 26 primes in arithmetic progression?
- P. Erdos and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.