Ha túlságosan nagy az n és a k, hogyan lehet kiszámolni n alatt a k értékét?

Nem tudom, mit nem lehet azon érteni, hogy ez nem egy precíz bizonyítás, csak egy szemléltetés...

Adtam másik bizonyítást, azzal már csak beéred.

Már mondtam hogy teljesen triviálisnak tekintesz dolgokat amik nekem nem azok.

"Úgy lehetett volna még folytatni, hogy az 5^n-eneket összeszorozzuk a számlálóban és a nevezőben (a többi 5-tel osztható számban lévő 5-ös tényező „elhanyagolható”),"

Például én ezt se látom be, hogy az valóban „elhanyagolható”.

"Mivel még viszonylag emberi számokról van szó, a konkrét példa egyik lehetséges bizonyítása, hogy a 2^100-nt, a 3^100-nt és ezek különbségét elosztjuk 5-tel, 25-tel, 125-tel, ... 5^n-nel, ezeket a hányadosokat egészre lekerekítjük, majd az így kapott kerekítéseket összeadva kapjuk, hogy a számig PONTOSAN hány darab 5-ös szorzótényező van."

Ezt se látom át, hogy mitől lenne ez igaz.

Továbbá ezt sem értem hogy a 100-as még kezelhető gépekkel, az ezres kitevő miért kezelhetetlenül nagy:

"Ezzel a bizonyítással csak annyi a gond, hogy egyrészt „csalnunk kell” (valamilyen segédprogramot fel kell használnunk), másrészt ha már nem 100, hanem 1000 lenne a kitevőben, akkor már ezt sem tudnánk használni."

>"Mivel még viszonylag emberi számokról van szó, a konkrét példa egyik lehetséges bizonyítása, hogy a 2^100-nt, a 3^100-nt és ezek különbségét elosztjuk 5-tel, 25-tel, 125-tel, ... 5^n-nel, ezeket a hányadosokat egészre lekerekítjük, majd az így kapott kerekítéseket összeadva kapjuk, hogy a számig PONTOSAN hány darab 5-ös szorzótényező van."

Ezt se látom át, hogy mitől lenne ez igaz.<

Az a te bajod. Ez az egy kijelentés mindentől függetlenül igaz.

Például nézzük meg, hogy A 3856*3855*... szorzat hány 5-ös prímtényezőt tartalmaz a fentiek szerint;

3856/5 = ~771

3856/25 = ~154

3856/125 = ~30

3856/625 = ~6

3856/3125 = ~1

3568/15625 = ~0, a többi hányados is ~0 lesz.

Összeadjuk a számokat: 771+154+30+6+1=962, tehát a fenti szorzat 962-ször osztható 5-tel, és 963-szor már nem.

Ha nekem nem hiszel;

[link]

[link]

(integer=egész szám)

"Ezt se látom át, hogy mitől lenne ez igaz."

Pedig az úgy jó, tökéletes. A baj a rákövetkező mondattal van:

"Abból pedig ténylegesen megmutatkozik, hogy hány nullára végződik."

Nem, mert 2-hatványra is el kell végezni, és a kisebb hatványkitevő lesz a nullák száma, vagyis nulla, mert

binomial(3^100, 2^100) = 2^0 * 3^100 * 5^14 * 7^22 * 11^17 * 13^14 * ...

Vagyis hiába lesz 5^14-gyel osztható, ha 2-vel nem, nem lesz nulla a végén. Tehát annyi tudható, hogy a szám 5-re végződik, de több nem.

Érdekességként: ha nem 10-es számrendszerben, hanem 3,5,7,11,13 alapúban nézzük, akkor 14+ nullára végződik.

"Pedig az úgy jó, tökéletes."

Kijött arra a példára, persze azt még nyers erővel ki tudtam próbálni gépen, hogy veszem a faktoriálisát és kapok egy "kilóméteres" számot, és ráeresztem hogy osztogassa 5-el, de akkor se értem miért jön ki. Ugyanazt a számot kipróbáltam 2-vel is, de nem egészre kellett kerekíteni hanem egészre kellett csonkítani úgy jött ki.

"Nem, mert 2-hatványra is el kell végezni, és a kisebb hatványkitevő lesz a nullák száma, vagyis nulla, mert"

Az meg hogy jön ki hogy az kisebb? Azért furcsa mert ugyan nem látom miért lenne igaz, de ha abból indulok ki hogy igaz, hogy úgy kijön azzal a módszerrel, akkor az megállapítható, hogy 2 hatványai lassabban növekednek mint 5 hatványai azaz kisebb számokkal osztogatod melyekből képzed az összeget, vagyis az összegnek többnek kéne lennie logikusan azaz logikusan több darab 2-esnek kéne lennie prímtényezőibe mint 5-ösnek.

A többi részéhez a konkrét feladatra is alkalmazva meg már fáradt vagyok.

Nem tudom mennyire vágod a Python-t, de amúgy egyszerű a feladat:

[link]

A //= helyben egész osztást jelent.

A kit_o kiszámítja, hogy n! p-nek hányadik hatványával osztható.

Ezt kiszámítjuk 3^100-ra (x), 3^100-2^100-ra (y), és 2^100-ra, a kombináció pedig p-nek (x-y-z)-edik hatványával osztható (sorvégen).

Pedig az egyszerűen kijön; hány 5-tel osztható szám van 1-től k-ig? Nyilván [k/5], ahol a szögletes zárójel azt jelenti, hogy az eredményt egészre lekerekítjük (alsó egészrész, a program -ha jól tudom- a floor paranccsal írja ki az eredményt).

Hány 25-tel osztható van? Nyilván [k/25]. Ezek a számok még egyszer oszthatóak 5-tel, tehát ezekből újra nyerhető fejenként 1-1 5-ös szorzó.

Ezt folytatjuk tovább az 5-hatványokkal (akár a végtelenségig, mivel egy idő után a lefelé kerekítés eredménye 0 lesz), és ezek összege adja meg, hogy 1-től k-ig hányszor tudjuk a számokat elosztani 5-tel összesen.

Nem gondoltam volna, kevesebb 2-es szorzó lehet benne, mint 5-ös, pláne nem azt, hogy egy darab sincs. Ez hiba volt.

Általában a „milyen számjegyre végződik” feladatokat úgy lehet megoldani, hogy a szám megfelelő maradékát keressük. Esetünkben a szám 100.000-rel vett maradékát kellene megtudnunk, vagyis a

(3^100 alatt a 2^100)/100.000 hányados maradékát. Ha valahogy sikerült kitalálnunk, hogy a számláló 5-ször osztható az 5-tel, akkor a törtet tudjuk egyszersíteni;

((3^100 alatt a 2^100)/5^5)/32, ahol ugyan most a számlálóban egy tört van, azt tudjuk, hogy annak a törtnek az értéke egész (mivel annyival osztottunk, hogy egész maradjon).

Nyilván a maradék ettől nem változik, viszont jelen helyzetben azt tudjuk, hogy a maradék legfeljebb 31 lehet, tehát az utolsó 5 számjegyek a 00000-től a 00031-ig lehetnek.

Hogy innen merre tovább, arra most nincs ötletem, de a semminél azért több.

" (alsó egészrész, a program -ha jól tudom- a floor paranccsal írja ki az eredményt)."

Az nem ír ki semmit, hanem az a floor függvény visszatér az az alsó egész részével, de az nem jó mert lebegőpontos, ekkora számoknál már túl pontatlan lenne. Egyébként ok kijön, értem. Akkor se azt mondtam hogy hiszem vagy nem hiszem hanem azt hogy nem értem a miértjét.

Hogyne ismerném a python-t, mielőtt megnéztem a válaszokat itt előtte ezt megírtam meg próbálgattam ezen függvényeket (python3 egyébként):

[link]

Egyáltalán bárki megoldotta ezt a feladványt? Hol láttad ezt a feladványt?

Mint ahogy több mindent nem vettem triviálisnak mint ami egyes válaszolóknak az volt, nem láttam be (még akkor) több állításról hogy azok igazak lennének. Ezek közül volt olyan állítás amiről kiderült hogy nem is igaz (prímtényezős felbontásába nem szerepel több kettes mint 5-ös, sőt nem is szerepel kettes).

Ha már python:

Kiszámoltam hogy nyers erővel kiszámolva csak maga a szám tárolása mekkora memória/tár igénnyel rendelkezne (Vagyis elegedően nagy ahhoz, hogy meg se próbáljam kiszámolni géppel, úgy is korlátokba ütköznék):

from mpmath import log,binomial,mp

mp.dps=31

print(log(binomial(3**100,2**100) , 256 ))

9 497 704 968 693 394 396 913 448 454 223 bájt azaz kb. 8.6*10^18 darab 1 terabájtos hdd/ssd kéne hozzá. (Még nem is úgy számoltam mint a gyártók szoktak 1000-el a prefixumokat, hanem 1024-el, vagyis valójában még több darab kellene belőle.)

Nem a legnaprakészebb cikk, de kb jó lesz: [link]

Ha milliárddal számolok hogy annyi terás háttértár van a világon összesen akkor még ennek is több mint milliárdszorosa a tárigénye csak magának a végeredménynek, az egyéb járulékos a számításhoz szükséges tárigény/memória azzal nem is számoltam. Számítási idő stb. arról nem is beszélve. Még ha több háttértár is van legyártva akkor se lőttem annyira mellé, azaz akkor is nagyságrendekkel kevesebb van mint amiken összesen egy bigdata rendszerbe építve a szám elférne.

Csak azért kérdeztem hogy bárki megoldotta e mert vannak olyan feladványok amiket még senki nem oldott meg. Pl. a prímfaktorizáció nehézsége amire épül az RSA (ilyet feladványt én is bármikor tudnék csinálni, eldobom a megoldást, így ha agyon ütnek se szedik ki belőlem, mert én se tudom, de könnyen ellenőrizhető egy megoldás jelöltről hogy megoldás e) : [link] .

Vagy az elliptikus görbéket "visszafelé" számolni is annyira nehéz, hogy a TLS biztonsági protokollra is használják.

A Goldbach-sejtést se bizonyította még be senki és még lehetne sorolni.