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.

DefinícióSzerkesztés

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

 

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.

TulajdonságaiSzerkesztés

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.

SejtésSzerkesztés

(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]

Kapcsolódó sorozatokSzerkesztés

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]

Kapcsolódó szócikkekSzerkesztés

JegyzetekSzerkesztés

  1. Mullin, Albert A. (1963), Recursive function theory (A modern look at a Euclidean idea), "Research problems", Bulletin of the American Mathematical Society 69 (6): 737, DOI 10.1090/S0002-9904-1963-11017-4.
  2. Factoring 43rd term of Euclid–Mullin sequence
  3. http://escatter11.fullerton.edu/nfs/forum_thread.php?id=102&postid=398#398
  4. a b c Factoring EM47
  5. The listing with the question marks is given in the Extensions field of the OEIS entry, whereas the main listing stops at 33 and has no question marks.
  6. Naur, Thorkil (1984), "Mullin's sequence of primes is not monotonic", Proceedings of the American Mathematical Society 90 (1): 43–44, DOI 10.2307/2044665.
  7. Guy, Richard & Nowakowski, Richard (1975), "Discovering primes with Euclid", Delta (Waukesha) 5 (2): 49–63.

További információkSzerkesztés