Факториал какого максимального числа можно сохранить? При хранении факториала некоторого натурального числа в k > 37 двоичных разрядах три старших бита были равны нулю, но факториал уже следующего числа сохранить в тех же k разрядах было невозможно. Позже было решено хранить в этих разрядах только значащие двоичные цифры факториала – без хвостовых нулей. Факториал какого максимального числа можно сохранить теперь. В случае, если правильных ответов несколько, то запишите ответ для минимально возможного значения k.

Предыдущий
вопрос Следующий
вопрос

Пусть n будет максимальным числом, факториал которого можно сохранить в k битах. Тогда факториал n+1 уже не помещается в k битах, поэтому (n+1)! требует k+1 бита. Обозначим количество бит, которые занимает факториал n как f(n). Таким образом, f(n) = k.

Так как три старших бита f(n) равны нулю, то длина (n+1)! не может быть равна k+1-3 = k-2 битам. Следовательно, (n+1)! занимает k-1 или k бит.

Учитывая, что любое натуральное число большее 3 имеет факториал, равный более чем 8, то (n+1)! требует k бит, и третий бит f(n+1) равен 1. Поэтому n+1 ≥ 6, и факториал 6, равный 720 = 1011011000 в двоичной системе счисления, занимает уже больше, чем k бит. Простейший способ хранить такой факториал – с использованием k+1 битов.

Таким образом, ответ: факториал 5 = 120 можно сохранить в 7 битах, но факториал 6 = 720 требует уже 10 битов.