Сколько нулей в конце факториала
Посчитайте множители 5 в n!, чтобы узнать число нулей в конце.
Дальше вы сможете получить точный ответ для 10!, 25!, 100! и любого другого факториала, не выписывая само огромное число.
В статье вы узнаете:
Два нуля в 10! можно увидеть без длинного умножения
Факториал n обозначают знаком ! и получают умножением целых чисел от 1 до n. Для десятки запись выглядит так:
В этой цепочке есть две пятёрки. Одну приносит число 5, вторую число 10, потому что 10 = 2 × 5. Двоек вокруг заметно больше: это 2, 4, 6, 8 и та же 10. Значит, для каждой пятёрки найдётся двойка, а из двух пар соберутся два множителя 10.
Полное произведение подтверждает вывод:
Число заканчивается двумя нулями. Но умножать всё подряд ради этих двух цифр не требовалось.
Первый пример можно проверить в калькуляторе факториала. Затем введите результат 3 628 800 в разложение на простые множители. Получится 2⁸ × 3⁴ × 5² × 7: пятёрок две, двоек восемь, поэтому полных пар 2 × 5 тоже две.
Каждый ноль в конце собирается из пары 2 × 5
Умножение целого числа на 10 сдвигает его десятичную запись на один разряд и добавляет справа ноль. Два множителя 10 дают два нуля, три множителя дают три. Поэтому задача сводится к вопросу: сколько раз число делится на 10?
Десятка раскладывается на два простых множителя:
Одинокая двойка нуля не создаёт. Одинокая пятёрка тоже. Нужна пара. У произвольного числа пришлось бы считать и двойки, и пятёрки, а затем брать меньшее количество.
У факториала есть удобная особенность. Множитель 2 встречается в каждом втором числе, а 5 в каждом пятом. Дополнительные двойки приходят из 4, 8, 12 и других кратных степеням двойки. Пятёрки тоже повторяются, но реже. Поэтому в n! двоек всегда хватает, и ответ ограничивает именно число пятёрок.
Это можно проверить без доверия к слову «всегда». Чисел, кратных 2, среди первых n не меньше, чем кратных 5. Чисел, кратных 4, не меньше, чем кратных 25. На следующем слое сравниваются 8 и 125, затем 16 и 625. Каждая степень двойки меньше соответствующей степени пяти, поэтому на каждом слое двойки встречаются чаще. Их общее количество тоже не может оказаться меньше.
Речь только о непрерывной цепочке нулей справа. Например, в числе 10 020 есть ноль внутри записи и один ноль в конце. Для делимости на 10 важен только последний.
Число 25 приносит две пятёрки, а 125 уже три
Попробуем тот же способ для 25!. Сначала отмечаем числа, кратные пяти:
На первый взгляд пятёрок пять. Но последнее число устроено иначе: 25 = 5 × 5. Одну его пятёрку мы уже посчитали вместе со всеми кратными 5, а вторую надо добавить отдельно. Получается шесть пятёрок и шесть нулей.
Точное значение подтверждает результат:
У числа 125 будет уже три пятёрки, потому что 125 = 5 × 5 × 5. Первый слой учтёт её как обычное кратное 5, второй добавит пятёрку за кратность 25, третий ещё одну за кратность 125. Именно поэтому одного деления n на 5 недостаточно.
Эту логику удобно представить как проход через несколько сит. Первое сито ловит все числа хотя бы с одной пятёркой. Сито 25 ловит дополнительную пятёрку у каждого кратного 25. Затем идут 125, 625 и дальше. Когда очередная степень пяти становится больше n, ловить уже нечего.
Общая формула складывает целые части делений
Чтобы посчитать пятёрки в n!, возьмите целую часть каждого деления:
Здесь floor означает число целых пятёрок, двадцать пяток или сотен двадцать пяток, которые помещаются в n. Остаток отбрасывается. Сумма заканчивается, когда делитель становится больше n.
Для 100! первый слой даёт 20 чисел, кратных 5. Среди них четыре числа кратны 25 и содержат ещё по одной пятёрке: 25, 50, 75 и 100. Степень 125 уже больше 100.
Значит, 100! заканчивается 24 нулями. Само число содержит 158 цифр, но для ответа понадобились два коротких деления.
Те же действия можно воспроизвести в калькуляторе деления с остатком. Введите 100 как делимое, затем по очереди 5 и 25 как делители. Складывайте только целые частные 20 и 4. Остатки здесь сообщают, почему неполная следующая группа не учитывается.
Для ручного расчёта достаточно короткого цикла. Начните с делителя 5, прибавьте целую часть, умножьте делитель на 5 и повторите. Даже у факториала с огромным n число шагов невелико, потому что делитель растёт как 5, 25, 125, 625.
Проверим алгоритм на числе, которое не заканчивается круглыми сотнями. Для 1234! получаются целые части 246, 49, 9 и 1 при делении на 5, 25, 125 и 625. Следующая степень 3125 уже больше 1234. Сумма равна 305, значит, именно столько нулей стоит в конце 1234!. Остатки 4, 9, 109 и 609 на ответ не влияют: каждый из них меньше очередной полной группы.
Размер самого факториала почти не влияет на длину расчёта. Число n может состоять из десятков цифр, а шагов будет столько, сколько раз пятёрку надо умножить на себя, чтобы превысить n.
Метод считает нули в десятичном n!, а не любые нули вообще
Формула со степенями пяти точна для факториала неотрицательного целого числа в десятичной записи. У 0! значение равно 1, поэтому нулей в конце нет, а сумма слагаемых пуста. Отдельно понять, почему 0! равно 1, можно через пустое произведение и число способов ничего не выбирать.
Для произвольного целого одной пятёрки уже недостаточно. Число 125 содержит три пятёрки, но не содержит ни одной двойки, поэтому не заканчивается нулём. Сначала надо разложить число на простые множители и сравнить количества двоек и пятёрок.
В другой системе счисления меняется и основание. В двенадцатеричной записи ноль в конце создаёт множитель 12, то есть набор 2² × 3. Десятичная формула с пятёрками там отвечает уже не на тот вопрос.
Есть и задачи, которые выглядят похоже, но требуют других методов. Эта сумма не находит нули внутри записи, не сообщает последнюю ненулевую цифру и не печатает сам факториал. Она отвечает ровно на один вопрос, зато делает это точно.
Проверьте метод на 250!
Целые части равны 250 / 5 = 50, 250 / 25 = 10 и 250 / 125 = 2. Следующая степень 625 уже больше 250. Сумма 50 + 10 + 2 даёт 62 нуля в конце, хотя выписывать 250! ради этой проверки совсем не хочется.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.