Mennyi legyen N ( + egész) minimális értéke, hogy N! osztható legyen 2^999000 * 3^499900 * 5^249990 * 101^9999 -el?

Használd ezt:

[link]

http://www.gyakorikerdesek.hu/tudomanyok__termeszettudomanyo..

Használd az ötödik válasz ötletét!

Triviális megoldás szorozgatni össze a számokat és nézni hogy osztható e.

Mivel a számok faktoriálisa felírható prím számok szorzatára ezért 2^999000 * 3^499900 * 5^249990 * 101^9999 számhoz azaz N tartozik mely 2^999000, 3^499900, 5^249990, 101^9999 számokhoz tartozó N-ek közül a legnagyobb. Ha nem a legnagyobb N-t venném ezek közül akkor a válaszott N! prímtényezői szorzatában egy vagy több különböző tényezőből kevés lenne azaz nem lenne osztató 2^999000 * 3^499900 * 5^249990 * 101^9999 számmal.

Sok félképpen próbálkoztam megoldani, a végtelen mértani sor csak közelítő megoldást adott, itt viszont pontos N kell.

"Szerintetek így jó?

n!-ban minden 3. osztható 3-mal, minden 9. mégegyszer,

minden 27. mégegyszer, stb. "

Ez nem ad jó megoldást.

Egyszerűség kedvéért nézzük minden 2-vel oszthatóval.

2^10-en re a legkisebb N mely N! modulo 2^10 = 0

10/2 + 10/4 + 10/8 = 8.75, egész osztással 8

A jó megoldás N=12

8! = 40320

8! mod 2^10 = 384

9! mod 2^10 = 384

...

12! mod 2^10 = 0 --> ez a jó megoldás

Minden 12-nél nagyobb N-re is jó, hiszen N! prímtényezőik tartalmaznak legalább 10 db 2-est.

Nézzük hogy jön ki az N=12.

A faktoriális szorzat szorzótényezőinek prímtényezős felbontásában kell összeszámolni a 2-eseket:

(10, 1) -> 2

(9, 2) -> 4

(7, 1) -> 6

(6, 3) -> 8

(3, 1) -> 10

(2, 2) -> 12

(0, 0) -> 12

Következő forában:

(2 aktuális hatványkitevője, hányszor fordul elő) -> aktuális N

2 aktuális hatványából levonjuk az aktuális N prímtényezőiben lévő 2-esek számát, addig haladunk míg el nem fogy 2 aktuális hatványa. A legutolsó N lesz a megoldás. Elég csak minden második N-re vizsgálni, a többiben úgy sem fordul elő.

Ugyan ez 2^50-re:

(50, 1) -> 2

(49, 2) -> 4

(47, 1) -> 6

(46, 3) -> 8

(43, 1) -> 10

(42, 2) -> 12

(40, 1) -> 14

(39, 4) -> 16

(35, 1) -> 18

(34, 2) -> 20

(32, 1) -> 22

(31, 3) -> 24

(28, 1) -> 26

(27, 2) -> 28

(25, 1) -> 30

(24, 5) -> 32

(19, 1) -> 34

(18, 2) -> 36

(16, 1) -> 38

(15, 3) -> 40

(12, 1) -> 42

(11, 2) -> 44

(9, 1) -> 46

(8, 4) -> 48

(4, 1) -> 50

(3, 2) -> 52

(1, 1) -> 54

(0, 0) -> 54

N=54

54! = 30 414 093 201 713 378 043 612 608 166 064 768 844 377 641 568 960 512 000 000 000 000

54! mod 2^50 = 0

53! mod 2^50 = 562 949 953 421 312

Dehát 54 jó megoldás

50/2 + 50/4 + 50/8 + 50/16 + 50/32 = 48.4375, egész osztással 47

(1/2+1/4+1/8 ...) végtelen sor határértéke 1, dehát maximum 50-et kaphatok, ha megszorzom 50-el. Több félképpen próbálkoztam nem csak 2 esetében, nem találtam rá képletet zárt alakba mellyel ki lehetne számolni és mindig jó megoldást adna. Maradt a brute force algoritmus ami rabszolga munka lenne kézzel, géppel már megoldottam. Leírjam a megoldást? Neked mi jött ki?