Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?


Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для его факториала нужно найти количество конечных нулей. Решение будет довольно простым — сумма: 

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...

Её мы можем обобщить в такую формулу:

$\sum\limits_{i=1}^\infty {N \over 5^i}.$

Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.

Почему в примере выше мы делим на 5? Потому что 10 может быть получено умножением 5 на 2. Поэтому полное решение будет иметь две формулы:

$\sum\limits_{i=1}^\infty {N \over 5^i}$

и

$\sum\limits_{i=1}^\infty {N \over 2^i}.$

Но, рассуждая логически, мы знаем, что первая сумма будет меньше, поэтому нам нужно посчитать только её (подробнее можно почитать тут).

Решение нашей проблемы


Для подсчёта конечных нулей факториала числа в определенной системе счисления я составил алгоритм, приведенный ниже:

  1. Разложить число B системы счисления на простые множители.
  2. Разделить число N на каждый уникальной простой множитель K, домножая K сам на себя до тех пор, пока $N \over K$ будет больше единицы, при этом округляя каждый результат до меньшего целого.
  3. Если при разложении числа системы счисления мы получили несколько одинаковых простых множителей K, то результат выше ��ы должны разделить на количество одинаковых K.
  4. Из всех делений N на каждый уникальный множитель K выбрать наименьшее частное, которое и будет нашим ответом.

Я покажу это на примере.
Пусть число N = 5, система счисления B = 12. Факториал 5! = 120, а 120 в 12-ой системе — A0. Мы видим, что в конечной системе счисления факториал исходного числа имеет один ноль. При разложении 12 на простые множители получим 2, 2, 3. У нас есть два уникальных числа: 2 и 3. Следуя нашему алгоритму выполним пункт 2 с числом 2.

${5 \over 2 } + {5 \over 4 } + {5 \over 8 } + ... = 2+1+0+... =3.$

Но двойка встречалась дважды при разложении 12-и, поэтому конечный результат мы делим на 2 и округляем до меньшего целого. В результате получаем 1.

Проделываем тоже самое с 3:

${5 \over 3 } + {5 \over 9 } + ... = 1+0+... =1.$

Таким образом, мы получили два частных от делений числа N на простые множители числа системы счисления. Они оба равны 1, поэтому меньшее нам выбирать не приходится и мы просто даем ответ — 1.

Рассмотрим еще один пример.

Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:

${16 \over 2 } + {16 \over 4 } + {16 \over 8 } + {16 \over 16 } + {16 \over 32 } + ... = 8+4+2+1+0+... =15.$

При разложении у нас было четыре двойки, поэтому сумму делений делим на 4 с округлением до меньшего целого: $ {15\over 4} = 3.$

P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.