Najlepsza odpowiedź
Były już odpowiedzi na to pytanie, ale nie mogę znaleźć żadnych. Spróbuję rozwiązać ten problem „od zera” w tej odpowiedzi.
Jest kilka sposobów rozwiązania tego problemu, zacznijmy od oczywistego sposobu: Oceń 30! a następnie użyj zwykłego algorytmu: podziel przez dwa, aż pozostanie niezerowa reszta. Chociaż ostatecznie doprowadzi to do odpowiedzi, 30! ma 33 cyfry, więc zajmie to trochę czasu.
OK, spróbujmy czegoś innego. Jaka jest potęga dwóch na 6 \ cdot 8? Cóż, jest to potęga dwóch na 6 plus potęga dwóch na 8, czyli 1 + 3 = 4. OK, możemy to wykorzystać do szybszego obliczenia naszej odpowiedzi. Od 30! = 1 \ cdot 2 \ cdot 3 \ cdots 28 \ cdot 29 \ cdot 30, możemy uzyskać odpowiedź, dodając odpowiedzi dla liczb od 1 do 30.
To by działało dość szybko, możemy uzyskać wynik w mniej niż minutę. Ale czy możemy zrobić lepiej? Oczywiście możemy! Jeszcze szybsze podejście poprawiłoby to ostatnie, zauważając, co następuje: Połowa mnożonych przez nas liczb (15) zawiera co najmniej jedną potęgę 2. Jedna czwarta liczb (zaokrąglona w dół, 7) zawiera co najmniej dwie. Jedna ósma (3) zawiera trzy. Jedna szesnasta (1) zawiera cztery.
Innymi słowy, połowa liczb zawiera co najmniej jedną potęgę dwójki. Połowa z nich zawiera dodatkową potęgę dwóch, połowa dodatkowych itd. Odpowiedź na nasze pytanie to 15 + 7 + 3 + 1 = 26.
Uwagi końcowe: Powinno być jasne, w jaki sposób można uogólnić to na podobne problemy, w których zmieniamy liczbę pierwszą (w tym problemie 2) na inną liczbę pierwszą, lub gdybyśmy pytali o większą silnię, na przykład 100 !. Na przykład potęga pięciu na 100! byłoby \ frac {100} {5} + \ frac {100} {25} = 20 + 4 = 24.
Odpowiedź
Musimy określić potęgę 2
Więc teraz zrobimy
= 30/2 + 30/2 ^ 2 + 30/2 ^ 3 + 30/2 ^ 4
= 15 + 7 + 3 + 1
= 26
Zatem 26 to potęga 2