Adott legkisebb valódi osztók távolságukat alkotó sorozat periódusának meghatározása és periódus hosszának meghatározása, hogyan?
Adott egy 1-n-ig terjedő természetes számokat tartalmazó intervallum.(Tegyük fel hogy n elegendően nagy a példák demonstrálásához, vagyis pl ha 2 mint legkisebb valódi osztója, azon számokat keressük akkor például n ne 3 legyen.)
Azon számok melyeknek 2 a legkisebb valódi osztója, ezek közül 2*2=4 a legkisebb, a többi mind 2-vel növekszik. Vagyis 4, 6, 8, 10 ... a távolságuk : 2, 2, 2, 2... vagyis a periódus hossza 1.
Azon számok melyeknek 3 a legkisebb valódi osztója 3*3=9 a legkisebb, a többi 6-al növekszik vagyis 9, 15, 21, 27, 33, 39, ... mivel mindig 6 a különbség a periódus hossza itt is 1.
Azon számok melyeknek 5 a legkisebb valódi osztója 5*5=25 a legkisebb. Aztán mindig 10-el növekszik vagyis 25, 35, 55, 65, 85, 95 ... a periódus hossza 1 ennél is.
Azon számoknál melyeknél 7 a legkisebb valódi osztó 7*7=49 a legkisebb. Ezen sorozat már komplikáltabb 49, 77, 91, 119, 133, 161, 203, 217, 259, 287, 301, 329 ...
A különbségük : 28, 14, 28, 14, 28, 42, 14, 42, ez ismétlődik.
Vagis a periódus hossz : 8.
Innestől kezve meg kompikált lesz már a sorozat, ha nagyobb számokra vagyok kíváncsi mint valódi osztó.
Hogy lehet ezt kiszámolni, erre milyen képletek vannak?
A legkisebb valódi osztó mindig prímszám. Azon számok melyeknek p a legkisebb valódi osztója ezek közül p*p a legkisebb.
"Aztán mindig 10-el növekszik vagyis 25, 35, 55, 65, 85, 95 ... a periódus hossza 1 ennél is."
Jav. : hol 10-el, hol 20-al növekszik vagyis a különbségük 10,20 ez ismétlődik, periódus hossz 2.
válasza:Ha jól értem: veszel egy p prímet, majd p többszörösei közül nézed azokat a számokat az [1, n] intervallumban, amelyknek nincs q prímosztójuk, ahol q < p. Ha valamiféle eloszlást akarsz meghatározni, akkor a szitálni kell szerintem.
Ez nem házifeladat kérdés (hanem eredetileg természettudományos kérdésnek írtam ki), csak áttették ami csacsiság volt.
Azzal a szitaformulával az adott [1,n] intervallumban lévő számok számát lehetne meghatározni méghozzá melyeknek p a legkisebb prímosztójuk. Az egymást követő ilyen számok különbségei (melyek periódikusan ismétlődnek, így a perióus hosszáról sem) nem mond semmit az a szitaformula.
Ha már szita az Eratoszthenész szitáját felhasználva ki lehet számolni, az említett periódust is valahogy lehetne definiálni hogy kell számolni, én csak intiutívan csináltam nem precízen matematikailag. Konkrét formulát viszont nem tudok rá, ezért kérdem.
válasza:Vegyed a p_1, p_2, p_3 ,... prímek növekvő sorozatát. Kijelölsz egy tetszőleges p_n prímet és szeretnéd megkeresni azokat az x számokat, amelyeknek p_n a legkisebb prímosztója. A kínai maradéktételre van szükséged, azaz:
x ≡ q_[1] mod (p_1)
x ≡ q_[2] mod (p_2)
.
.
.
x ≡ q_[n-1] mod (p_n-1)
x ≡ 0 mod (p_n)
egyenletrendszert kell megoldani, ahol q_[i] -k egyike sem nulla.
És ezt az összes lehetséges (q_1, q_2, ..., q_n-1) kombinációra el kell végezned.
Ezen megoldások uniója lesz az x-ek halmaza, ami valójában véges sok számtani sorozat uniója.
Az egyik hozzászóló által írt szitaformula használata nagyon nem hatékony.
Ez a kínai maradéktételes megoldás pedig borzasztó lassú lenne, exponenciális robbanás már csak az ahány kongurenciarendszert kell megoldani.
Mivel nem arra vagyok kíváncsi, hogy lehet rosszabb futási idővel azaz kevésbé hatékonyan ugyanazt megcsinálni. Így akkor inkább marad az ezeknél jóval gyorsabb az Eratoszthenész szitájának módosítása, mivel úgy látom ennél nem tud itt senki hatékonyabbat. Méghozzá a cella sorszáma reprezentálja az adott természetes számot, a cellába írt érték a legkisebb annak osztója. Ha nincs még beleírva szám akkor kerül bele az adott p szitálandó értékkel. p=2-vel végig lehet menni majd p=3 és nagyobb p estében 2*p lépésközzel is triviális, hiszen a többit kár ellenőrizni triviálisan mert osztható kettővel. Minden p prím celléjába az adott prím kerül majd p*p indexű cellba kerül p prím (ezt vakon elhisszük, ellenőrizni se kell), majd ellenőrizve p*p-től 2*p lépésközzel haladunk.
válasza:@21:09
Kedves doktor úr/nő hozzászóló!
Én az adott legkisebb osztóval rendelkező számok távolságának periódikus ismétlődésének periódushosszának számítását, ezen távolságok tagjainak számítására kerestem képleteket ahogy a kiírt kérdésemben konkrét példákkal is szemléltettem. Valójában egyik válaszban említés szinjén sincs benne a kérdésben megfogalmazott periódus.
válasza:@09:31
Ha például a 7-re keresem a periódust:
Az egyik kongurencia rendszer :
x ≡ q_[1] mod 2
x ≡ q_[2] mod 3
x ≡ q_[3] mod 5
x ≡ 0 mod 7
Mi a q_[1], q_[2], q_[3] ?
válasza:További kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!