Számelméleti módszerekkel ki lehet számolni, hogy 9! -nak hány számjegye van, és mi az utolsó számjegye?
9!! = (9!)! = 362880!
Sajnos sem a számológép, sem a számítógépen lévő számológép nem tudja kiszámolni, gondolom mivel olyan nagy szám. A kérdésem tehát az, hogy valamilyen számelméleti módszer segítségével ki lehet számolni, hogy ennek az értéknek hány db számjegye van, és hogy az utolsó számjegye micsoda? Illetve meg lehetne-e állapítani, hogy az n-dik számjegye mi?
Olvastam valahol, hogy meg lehet ilyeneket valahogyan állapítani, tudom hogy nagyon nehéz, de esetleg egy olyan valaki, aki ért a matekhoz, talán képes rá.
válasza:> „Egyáltalán nem bonyolult: ”
Jaja, én is ezért gondoltam, hogy hagyom gondolkozni a kérdezőt.
Viszont az n-edik jegy kérdése érdekes. Tudsz rá valami jó algoritmust? Mert én erősen azt sejtem, hogy ki lehet hozni polinomidőben.
"Végtelen sok időm sajnos nincs, majd 5-6. osztály környékén megtanulod (oszthatóság, prímtényezős felbontás,…), hogy hogyan kell a nullák számát kiszámolni a végén"
Nos, valójában én már leérettségiztem már 3 éve, de azóta nem igazán foglalkoztam a matematika ezen részeivel, sőt bevallom, közvetlenül érettségi után sem tudtam volna megcsinálni ezt a feladatot, ahogy a legtöbb műszaki főiskolás ismerősöm se, ugyanis egyáltalán nem is tanultunk ilyesmiket. Pl mi középsuliban a valószínűségszámítást teljesen ki is hagytuk, ahogy még nagyon sok mindent, ráadásul általános iskolában egyáltalán nem tanultunk ilyesmit, az oszthatóságból csak az alapok voltak, azaz tört osztása törttel, meg prímtényezős felbontás, és semmi több. A műszaki főiskolára járok, de a csoporttársaim nagy része nem ismeri a másodfokú egyenletrendszer megoldóképletét, és a középiskolás matematikát sem nagyon értik. Nem vagyok valami zseni matekból, de még nekem megy a legjobban, sőt még jobban menne, ha nem fogtam volna ki olyan osztálytársakat, akik miatt nem lehetett tanítani. De ez mindegy is. Lehet hogy már 9-10 éve meg kellett volna oldanom olyan feladatokat, mint ez, de azt azért tudjátok meg, hogy a főiskola ahova járok, tele van olyanokkal, akik még annyira sem értenek a matekhoz, mint én. Tudom hogy ijesztő, de ez van. Nem bántásból mondom, nem haragudtam meg senkire, hogy 10 évesnek sem gondoltatok, inkább csak magamra haragszom, meg a környezetemre, amiért sem diákokból, sem tanárokból nem a legjobbakat fogtam ki (hanem a lehető legrosszabbakat), és hogy bizonyos matematikai témakörökből egy alsós tagozat szintjén vagyok, és rajtam kívül még a főiskolában tanulók 99%-a.
válasza:#12: Nem tudom.
Az első néhány ezer számjegy a Stirling-formulával kiszámítható, ill. az utolsó, nem nullák is, de mondjuk a középsők kiszámítására nem látok módot, az előtte, vagy utána lévők kiszámítása nélkül.
Ennél a számnál az összes (alig 2 millió) számjegy kiszámítása is lehetséges, de pl. (20!)! középső számjegyei aligha.
Szerintem ezek(középsők) kiszámítási ideje exponenciálisan nő.
Még arra sem jöttem rá, hogy a WoframAlpha hogyan számolja ki ezeket: "Last non-zero digits:"
Ha van ötleted...
válasza:Moduló valami hatványozgatni lehet nagyon gyorsan, valami Fibonacci-számos kérdésnél itt is mutattam egy algoritmust. Az a lényeg, hogy ha érdekel x-nek mondjuk a 100. hatványa moduló m, akkor kiszámolod gyorsan x2 = x*x-et, x3 = x2*x2 = x^4-t, x4 = x3*x3,… ugye moduló m, ezzel úgy meglesz 8 lépésből meglesz x, x^2, x^4,… x^64. 100 kettes számrendszerben 1100100, azaz 64+32+4, tehát x^100 = x^(64 + 32 + 4) = x^64*x^32*x^4 = x9*x8*x3. Ha csak moduló m kell, akkor mindig elég egy-egy log(m) jegyű számot szorozni egy log(m) jegyű számmal. Tehát x^sok utolsó számjegyeit nagyon gyorsan ki tudjuk számolni.
n! mondjuk utolsó nem nulla jegyeinek számolásához azt kéne csinálni, hogy n-ig összeszámoljuk, hogy hány darab szám végződik 001-re, 002-re, 003-ra,… aztán kiszámoljuk ezeknek a hatványait moduló 1000 és összeszorozzuk őket. Persze például a 10-et 001 végűnek kéne venni, meg figyelni kell az 5-ös végződésekre meg ilyenek, de talán így már nem olyan reménytelen.
(((És akkor itt még megjegyzem, hogy m^n tényleges kiszámolása azért reménytelen, mert m^n jegyeinek száma exponenciálisan nő m és n jegyeinek számával, tehát az output hossza is exponenciális függvénye az input hosszának, így a kiszámolása is exponenciális időt vesz igénybe. Hasonlóan n! pontos kiszámításához. Viszont n! k-adik jegyének kiszámíthatóságában éppen azért reménykedem, mert az gyakorlatilag csak egy 3 bites információ. Persze nem biztos, hogy igazam van, és lehet, hogy annak kiszámolása sem megy polinomidőben.)))
U.i.: Bocsánat, ha zagyvaléknak tűnik, kicsit kába vagyok…
válasza:"Végtelen sok időm sajnos nincs, majd 5-6. osztály környékén megtanulod (oszthatóság, prímtényezős felbontás,…), hogy hogyan kell a nullák számát kiszámolni a végén"
Ez a válasz nagyon vicces, szerinted alsósok használnak olyan kifejezéseket, hogy "számelméleti módszer"??
válasza:#16: Igen, én is így gondoltam, ill. tudnám kiszámolni, de a Wolfram az utolsó 13 jegyet kiírja, az pedig ilyen módszerrel nem menne.
Tehát tudnak még valamit, amivel ez egyszerűbben is megy.
válasza:Kapcsolódó 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!