Prímek számtani sorozata

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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 pk 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.

Legnagyobb ismert AP-k (2016.03.)[5]
k Prímek n = 0 – k−1 Számjegyek Év Felfedező
1 257885161 + 422·n − 1 17425170 2013 GIMPS, Curtis Cooper
2 243112609 + (257885161 − 243112609n − 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·225000n − 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.

Legnagyobb ismert CPAP-k (2016.03.)[11]
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]

  1. 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
  2. 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.
  3. Lásd H. J. Weber, ``Less Regular Exceptional and Repeating Prime Number Multiplets," arXiv:1105.4092[math.NT], Sect.3.
  4. http://primerecords.dk/aprecords.htm
  5. a b c d e f Jens Kruse Andersen, Primes in Arithmetic Progression Records. Retrieved 2015-12-05.
  6. John, AP26 Forum. Retrieved 2013-10-20.
  7. Wroblewski, Jaroslaw (2008-05-17), "AP25", primenumbers mailing list
  8. Wroblewski, Jaroslaw (2007-01-18), "AP24", primeform mailing list
  9. 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.
  10. Manfred Toplic, The nine and ten primes project. Retrieved on 2007-06-17.
  11. Jens Kruse Andersen, The Largest Known CPAP's. Retrieved on 2014-06-13.

Irodalom[szerkesztés]