Hogy lehet adott n tartományon belül azon számoknak a melyeknek k a legkisebb k (k>1) osztója a differencia sorozatának a periódushosszát és periódusát meghatározni gyorsabban mint ami triviális?

Megkülönböztethetjük azon módszert ahol adott k-t számoljuk és ahol adott k-t és k alattiakat is. A triviális módszer szerint "különösebb" overhead nélkül számítható k és k alatt is a csak kimondottan k-ra számításához képest.

Így feltételezek olyan nem triviális módszert, ahol adott k-ra gyorsabb mint a triviális szerint, de az adott k-ra és a k alattiakra összesen meg a triviális módszer a gyorsabb.

Olyat tudok ami kevésbé triviális, de "visselkedésre" nem olyan mint amit feltételezek hogy létezik (de nem tudok).

A kevésbé triviális az hogy osztás nélkül (négyzetgyökvonást használ) gyorsabb:

Azon osztók meghatározásához melyek szerepelni fognak : Adott n korlát egész értékű négyzetgyökvonásáig (isqrt) csináljunk Eratoszthenész szitáját.

Vegyünk egy n elemű üres elemeket tartalmazó listát. 3-tól felfele 2 lépésközzel töltsük fel értékekkel.

Az előzőleg meghatározott prímlista szerint a p legnagyobb négyzetétől azaz p^2-től számítva 2*p lépésközzel írjuk bele p-t.

Ezt ismételjük folytassuk p=3-ig.

Majd 2-től 2 lépésközzel írjuk bele a 2-őt.

A fordított bejárás arra alapszik, hogy karakterisztikusan ugyanannyi munka nézni egy cellát hogy van e benne már érték mint azt felülírni, így nem kell nézni sosem, a kisebb felülírja a nagyobbat. A 2*p lépésköz meg azért kell, mert a többi úgyis páros lenne ahol tudjuk, hogy a 2 kell.

Ezek alapján listákat kell építeni ami triviális, a többi része is az, külön nem részletezem.

@16:27

Köszi a választ.

"Ennek nem sok értelmét látom, végtelen, vagy elegendően nagy n esetén van értelme."

Például, ha n=200 akkor 7-re a differencia sorozat : [ 28, 14, 28, 14, 28, ] , naivan kijön a ciklus hossz 2-nek így.

Ez 2 egymással szemben álló tulajdonság, hogy elegendően nagy és a megfelelően kicsi. Első megközelítésben (naivan) nem lehet tudni, hogy adott n elegendően nagy e, hiszen ha 1000x ismétlődött a ciklus n-ig nem vagyok benne biztos hogy nagyobb n-re 1001x is ismétlődni fog, hiszen ha nem akkor nem az volt a ciklus. Ez volt a gondolatmenet mögötte, bár nem gondoltam komolyan hogy ténylegesen így is van, de mint első megközelítés szintjén ez még kérdéses.

"Mivel minden elem 2p (=26) többszöröse, ezért ezzel osztva a listaelemeket egy sokkal egyszerűbb, átláthatóbb listát kapnál"

Igen, de az így már másik lista. Így lesz ugyanaz csak máshogy felírva pl. : t=26 2t,1t,2t,3t,1t,3t,2t,1t,...

"Vagyis primoriális-szerűen nő. (Az előző prím -1 a szorzó)"

Bejött a hipotézisem, hogy gyorsabban is lehet számolni a hosszt mint magát a sorozatot.

A sorozat számítására melyben p a legkisebb (p>1) osztó n korlátig még azt találtam ki, hogy venni kell az előforduló összes kombinációban a prímszámok szorzatát. Kezdve az egytényezős szorzattal (ami maga p) majd az összes 2 tényezős szorzatot p*p , p*next_prim(p) ... összes 3 tényezős szorzatot stb. , a végén sorba rendezni.