Eukleidész–Mullin-sorozat

Az Eukleidész–Mullin-sorozat egy prímszámokból álló, ismétlődést nem tartalmazó sorozat, melynek minden eleme a korábbi elemek szorzatánál eggyel nagyobb szám legkisebb prímtényezője. Nevét a végtelen sok prímszám létezését igazoló ókori görög matematikusról, Eukleidészről, valamint a sorozat ötletét 1963-ban felvető kanadai matematikusról, Albert A. Mullinról kapta.^[1]

A sorozat első 51 eleme a következő:

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357, 87991098722552272708281251793312351581099392851768893748012603709343,^[2][3] 107, 127, 3313, 227432689108589532754984915075774848386671439568260420754414940780761245893,^[4] 59, 31, 211... (A000945 sorozat az OEIS-ben)

Ezek a sorozat ismert elemei (2016. november). A következő elem megtalálásához egy 335-jegyű összetett szám legkisebb prímtényezőjét kellene megtalálni.

Jelölje a_n a sorozat n-edik elemét, ekkor a_n a következő szám legkisebb prímtényezője:

${\displaystyle \left(\prod _{i<n}a_{i}\right)+1\,.}$

Az első elem tehát az üres szorzat plusz 1 legkisebb prímtényezője, azaz 2. A sorozat 13-as értékű tagja így kapható meg: 2 × 3 × 7 × 43 + 1 = 1806 + 1 = 1807 = 13 × 139.

A sorozat végtelen, és nem tartalmazza kétszer ugyanazt az elemet. Ez igazolható Eukleidész végtelen sok prímszám létezését igazoló bizonyítása segítségével. A bizonyítás konstruktív és a sorozat épp a konstrukció egy változata.

(Mullin 1963) tette fel a kérdést, hogy vajon minden prímszám szerepel-e az Eukleidész–Mullin-sorozatban, és ha nem, vajon adott prímszámról kiszámítható-e, hogy tagja-e a sorozatnak; ezek a kérdések máig nyitottak. A legkisebb prímszám, amiről nem ismert, hogy tagja-e a sorozatnak, a 41.

A 100-nál kisebb prímszámok pozíciói a sorozatban:

2:1, 3:2, 5:7, 7:3, 11:12, 13:5, 17:13, 19:36, 23:25, 29:33, 31:50,^[4] 37:18, 41:?, 43:4, 47:?, 53:6, 59:49,^[4] 61:42, 67:?, 71:22, 73:?, 79:?, 83:?, 89:35, 97:26 (A056756 sorozat az OEIS-ben), ahol a ? arra utal, hogy az adott prímszám sorozatbeli pozíciója, illetve hogy egyáltalán tagja-e a sorozatnak, jelenleg nem ismert.^[5]

A második Eukleidész–Mullin-sorozatnak hívott sorozat tagjait úgy határozzuk meg, hogy az előző elemek szorzata plusz 1-nek nem a legkisebb, hanem a legnagyobb prímtényezőjét vesszük. Az előző sorozatnál gyorsabban növekszik, de szintén nem monoton,^[6] továbbá ismert róla, hogy nem tartalmazza az összes prímszámot. A sorozat első néhány eleme:

2, 3, 7, 43, 139, 50207, 340999, 2365347734339, 4680225641471129, 1368845206580129, 889340324577880670089824574922371, … (A000946 sorozat az OEIS-ben).

Egy másik változtatással, ha nem végezzük el a prímtényezőkre bontást, hanem minden elem az összes előző elem szorzata plusz 1, akkor a Sylvester-sorozatot kapjuk. Az a sorozat pedig, amikor a korábbi számok szorzata plusz 1 összes prímtényezőjét vesszük sorban, a Sylvester-sorozat prímtényezőit adja ki. Az Eukleidész–Mullin-sorozathoz hasonlóan prímek nem monoton sorozatát kapjuk, de erről ismert, hogy nem tartalmazza az összes prímszámot.^[7]

• Eukleidész-féle szám

• Weisstein, Eric W.: Euclid–Mullin Sequence (angol nyelven). Wolfram MathWorld
• A. R. Booker, S. A. Irvine: The Euclid-Mullin graph
• Factoring 43rd Term of Euclid–Mullin sequence, factorizations of the numbers for which the sequence elements is the smallest prime factor