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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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)
[szerkesztés]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
[szerkesztés]Jegyzetek
[szerkesztés]- ↑ 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
- ↑ a b c d e f 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
[szerkesztés]- 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.