Формула Лежандра

Часто в математических кружках дают задачу определить, на сколько нулей заканчивается число 100!.
(Восклицательный знак означает факториал. В частности, 100!=1*2*3*...*99*100, т.е. произведение натуральных чисел от 1 до 100.)

Школьникам надо заметить, что число заканчивается на k или больше нулей, если в его разложении на множители входит минимум k двоек и минимум k пятёрок.
Следующим продвижением будет соображение, что пятёрки встречаются реже, поэтому надо определить, на какую максимальную степень пятёрки делится 100!.

Пятёрки входят в числа, кратные пяти (не очень неожиданно, правда?). Их ровно 100/5=20.
Задача решена?

А вот и нет! Ведь есть числа 25, 50, 75, 100, в которые пятёрка входит аж два раза!
А три раза пятёрка входит в 5^3=125, но никак не раньше.

Поэтому ответ на вопрос первой задачи - 100/5+100/25=20+4=24.

Теперь давайте попытаемся немного обобщить задачу и ответить на вопрос, на какую максимальную степень простого числа p делится n! (напомню, что число называется простым, если оно делится только на единицу и на само себя).

На p делится каждое p-е число. А их ровно [n/p] ([x] означает целую часть числа x, т.е. минимальное целое число, не превосходящее x.)

Зачем нужна целая часть? Ну, например 100 на 23 не делится. Поэтому, 23 как множитель входит только в числа 23, 46, 69, 92. По другому, [100/23]=4.

Но ведь, как и в задаче про 100!, число p может входить в числа p^2, 2p^2, 3^2, ...
Сколько таких чисел? А их ровно [n/p^2].

Аналогично, три раза число p входит в разложение n! ровно [n/p^3] раз и т.д.

Таким образом, мы доказали формулу Лагранжа:

ord(n!,p)=[n/p]+[n/p^2]+[n/p^3]+...

Здесь ord(n!,p) означает степень вхождения простого числа p в n!.

Кажется, что ничего сложного?

Но эта формула решает задачу не только из моего поста про постулат Бертрана, но и задачу с последней Международной математической олимпиады школьников!

Решите в натуральных числах уравнение

k!=(2^n-1)(2^n-2)(2^n-4)*...*(2^n-2^(n-1)).

Справитесь?