A mai matematikában szerepel -e a következő észrevételem: háromnál nagyobb prím számok csak a hattal osztható számok közvetlen közelében (=+-1) lehetnek? Ez ugyanis erősen devalválná az ikerprímekre tett észrevételt...

Láttam régebben next prime implementációt. Azaz az adott n számnál nagyobb prímszámok közül a legkisebb ilyen prím kereső algortumust. A nem egész input külön lekezelése meg a rendhagyó eseteket leszámítva magától értetődő hogy 2 lépésközzel lépkedve haladjon a prím validátort csak azokra hívja meg azaz csak a páratlan számok nézze hogy prím e, párosakra vakon elhisszük hogy nem lehet prím, ezért meg se kell hívni rájuk a validátort. Az implenetáció azonban úgy csinálta hogy a lépésközök nem konstans kettő hanem 2, 4, 2, 4 ... . Ez pont annak következménye, hogy egy olyan sorozat mely a 2-vel és 3-al osztható számok kivételével a többi egészet tartalmazza 5-tól kezdve a sorozat : 5, 7, 11, 13, 17, 19, 23, 25 ... így elég csak ezeket ellenőrizni hogy prímek e.

Én már régen ezt tovább gondoltam és általánosítottam, amit most előkerestem. Ilyen elven az első k darab prímszám szűrésére algoritmust, lépésközök megadásával. Ilyen nagy gyorsító táblázatok lesznek, exponenciális robbanással nőnek k függvényében.

A k=2 esetén :

szitáló tagok listája : (2, 3)

periódikus ismétlési hossz : 6 azaz 6 hosszú intervallumban ismétlődik hogy mit szitált ki mit nem

ciklusan ismétlődő lépésközök listája : (2, 4)

tetszőleges számtól hogy gyorsan lehessen számolni gondolkodás nélkül csak gépiesen és általános esetre is nagyobb k-ra is, kell venni a kezdő szám legyen n moduló periódushossz azaz k=2 esetében moduló 6 azaz leírva n mod 6 és a számhoz leközelebbi ilyen tag ahonnan kell kezdeni az előszitálást ennek gyorsítólistája (1, 0, 3, 2, 1, 0) pl ha n mod 6 = 0 akkor 1-et kell hozzáadni, ha n mod 6 = 1 akkor 0-át kell hozzáadni, ha n mod 6 = 2 akkor 3-at kell hozzáadni. azaz n + (1, 0, 3, 2, 1, 0)[n mod 6] ahol [ ] az index operátor, aki programozott már tömbökkel az tudja. ez a táblázat meg a (2, 4) táblázatból jön ki úgy hogy egyesével csökkentem 0-ig tagonként és a közbenső kapott értékeket is tartalmazza, kivéve a kiindulási értéket így rendre : 2-őt nem 2-1 = 1 ezt igen 1-1=0 ezt is. A 2-vel végeztünk, jön a 4. 4 az nem, 4-1=3 ez igen, 3-1=2 ez igen stb. így 0-ig.

Van még egy gyorsító táblázat, ez arra van hogy ész nélkül csak gépiesen táblázatból numperikusan gyorsan lehessen dolgozni. Ez meg azt adja meg hogy (2,4) gyorsítólistának hanyadik tagjától kell számolni egy adott n számtól kezdve. 2 a nulladik 4 az első tag.

Erre a gyorsító indexlista : (0, 0, 1, 1, 1, 1).

Azaz (0, 0, 1, 1, 1, 1)[n mod 6].

Ezeknek a gyorsítólistáknak inkább akkor van jelentősége ha k>2.

k=3

szitáló tagok listája : (2, 3, 5)

periódikus ismétlési hossz : 30 ( kijön különben ez így : 2*3*5)

ciklusan ismétlődő lépésközök listája : (2, 6, 4, 2, 4, 2, 4, 6)

előszitálás inexekhez gyorsítólista : (1, 7, 11, 13, 17, 19, 23, 29)

Ezt (1, 0, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0) a hosszú kolbászt jelölöm l-el.

Az n mint természetes szám, n-nél nagyobb vagy egyenlő a 2, 3, 5-el nem oszható számok közül a legkisebb amit megkapunk úgy hogy n+l[n % 30].

Remélem jól írtam olyan értelemben, hogy nem fogalmaztam félre.

Egyébként már régebben implenetáltam pythonba, randomizált teszteken átment más előre legyártott prímkeresőkkel összehasonlítva, de ez csak az előszűrés, ez tartalmazhat nem prímeket is. Igazából ez gyorsít valamit ahogy növelem k értékét, de ott ahol égetőbb a sebességkérdés ott nem segít a nagyon nagy számoknál, pedig az kioptimalitált c-ben meg nem próbaosztásokkal (nem én csináltam) prímtesztelő. Amit ez kiszitált nagyon nagy számoknál a prímteszelő is gyors végezne velük ha azokra is meghívnám, a prímek teszelése viszi el az időt, de itt több száz jegyű számokról beszélek.

k=13-ra vettem, ennél többnek empírikusan nem látom értelmét, még lehet ez is túlzás, akkora hozama sebességnövekedésben ennek sincs mint gondoltam.