Сколько цифр в числе 100!?

Квант 1988, №7 с. 57-59 Тег CUF9

В. Н. КАСАТКИН

Кажется, на этот вопрос получить ответ легко. В самом деле, ниже приведется программа — вычисление факторials числа $N$ ; работа по такой программе, компьютер вычислит и выведет на экран или напечатает число 100!. Нам останется только подсчитать число цифр в выведенном машиной числе.

Но попытки применить этот подход к большим числам $N$ приводят к неудачам — дело в том, что персональные компьютеры в большинстве своем не могут вывести на экран число, содержащое более 15 цифр.

Вот факторials нескольких чисел, больших 10, вычисленные на ЭВМ типа «Корвет»:
$10! = 3628800;$
$11! = 39916800;$

$12! = 479001600;$
$13! = 6227020800;$
$14! = 87178291200;$
$15! = 1307674368000;$
$16! = 20922789888000;$
$3.55687428096E+14 = 17!$

ФакторIAL числа 17 уже не помещилися на экран — произшло переполнение разрядной сетки и компьютер вместе точно результата 355687428096000 выдал значение числа 17! в нормализованной форме. ЭВМ предложила нам считать, что
$17! = 3.55687428096E+14 = 3,55687428096 \cdot 10^{14}.$

Означает ли это, что мы в принципие не можем на компьютере получить факторIAL большого числа, например 100!. Ответ простой: нет, не означает. Мы можем с помощью ЭВМ получить полную запись числа 100!, не потеряв ни одной цифры.

Это достигается путем использования программыстской смекалки. Задача, которую мы собираемся решить,

Рис. 1.

весьма примечательна для программыирования. Речь пойдет о том, как человек использует ЭВМ: действует ли он по шаблону или же, вникнув в особенности машин, заставляет ее работать необъчно, нестандартно.

Прежде чем расскаазать о практически природной программе нахождения всех цифр числа 100!, например о нескольких необходимых в дальнейшем средств языка Бейсик.

В программе будет использована функция «целая часть от значения аргумента». В Бейсике эта функция обозначает INT(X) — для любого действительного X значение функции INT(X) равно целому значению X, не превышающего его, например:

$\text{INT}(2.5) = 2, \text{INT}(0.002) = 0,$
$\text{INT}(-6.3) = -7.$

Условия все цифры получаемых факторалов чисел считать значениями переменных $a_i$ , где $i=1, 2, \ldots$ . До начала вычисления $N!$ каждая переменная $a_i$ равна нулю; начнем вычисления (рис. 1).

В процессе вычисления значения переменных $a_i$ изменяются.

Напомним, что если известен факторал числа $(k-1)$ , то легко найти факторал числа $k$ :

$k! = k \cdot (k-1)!.$

Приименим это правило к получению 4!, если известно, что 3!=6. Действует так: 6 умножаем на 4 и получаем 24. Цифру 4 делаем значением переменной $a_1$ , а цифру 2 — значением переменной $a_2$ . Схематически все эти действия можно изобразить так, как показано на рисунке 2.

Продолжим работу: вычислим 5!. Для этого 4!=24 умножим на 5 и соответствующие цифры делаем значениями переменных (см. рисунок 3).

Примотримся внимательнее к процессу переменжения чисел $k$ и $(k-1)!$ . Умножение одного многоразрядного числа на другой сводится к умножению и сложению цифр. При этом мы хорошо различаем цифру младшего разряда и цифры старших разрядов.

Пристановим обсуждение задачи в целом и научимся решать небольшую, но важную для дальнейшего задачу: научим вычислительной машину выполнять выделение цифры десятков и цифры единиц в двухразрядном десятичном числе.

Необходимо составить программу, работа по которая, ЭВМ, после предъявления ей двухразрядного числа, переменной $a_1$ приводит значение, равное числу единиц, а переменной $a_2$ — значение, равное числу десятков.

Пусть переменная $A$ имеет значение, равное двухразрядному десятичному числу (например 73). Разделим значение $A$ на 10 и от результата возьмем целую часть — это и будет цифра десятков:

$\text{LET}A(2) = \text{INT}(A/10),$
$\text{t. e. } a_2 = [7,3] = 7.$

Если теперь от значения $A$ obtains $a_2 \cdot 10$ , то получится цифра единиц в исходном числе $A$ :

$\text{LET}A(1) = A - A(2)*10,$
$\text{t. e. } a_1 = 73 - 7 \cdot 10 = 3.$

Вернемся к задаче получения числа 5! Мы помним, что для этого придается число 4!=24 умножить на 5. Помним мы и о том, что число

Рис. 4.

4!=24 хранится необъчно: цифра 4 есть значение переменной $a_1$ , а цифра 2 — значение переменной $a_2$ . Можно образно сказать, что цифры 2 и 4 хранятся в ячейках $a_2$ и $a_1$ соответственно.

Умножив содержимое ячейки $a_1$ на 5, мы получим двухразрядный результат: $4 \times 5=20$ . Цифру младшего разряда (это в данном случае — ноль) будем считать новый значением переменной $a_1$ , а цифру 2 удержим пока «в уме». После этого следует выполнить умножение цифры, хранящейся в $a_2$ , на 5 и к получению произведение прибавить цифру 2, предварительно взяв ее из нашей памяти. Результат действия: $5!=5 \cdot 4!=5 \cdot 24=120$ (рис. 4). После выполнения всех действия переменные $a_1$ , $a_2$ и $a_3$ получили новые значения $a_1\neq0$ , $a_2=2$ и $a_3=1$ .

Если даже число $(k-1)$ ! содержит не две, а три и более цифр, схема получения цифр числа $k$ ! остается прежней (рис. 5).

Рис. 5.

центы $m_i$ могут быть многоразрядными числами.

Использовать следующий текст программы:

REM ВЫЧИСЛЕНИЕ ФАКТОРИАЛА ЧИСЛА N
DIM A(100)
INPUT N
FOR I=2 TO 100
A(I)=0:NEXT I
A(1)=1:L=1
FOR K=1 TO N
R2=0:R1=0:I=1
IF R2=0 THEN IF I&gt;L THEN 80
R=A(I)*K+R2
R2=INT(R/(10000!))
R1=R-R2*(10000!)
A(I)=R1
I=I+1
GOTO 40
L=I-1
NEXT K
FOR J=1 TO I-1
PRINT A(I-J);
NEXT J
END

В результате примения программы получим*:

100!=93 326215 443944 152681 699238 856266 700490 715968 264381 6214
963 895217 599993 229915 608941 463976 156518 286253 697920 8272
251 185210 916864 0 0 0

Естественно, что число $k$ может быть не только однозначным, а и двухразрядным. В этом случае коэффициенты Itak, у числа 100! имеется 158 цифр — понятие гипантское число!

*) Машина, распечатьая число, записьает его группами по 6 цифр, пропуская при этом начальное нулевую Так, в приведенной распечатке группу цифр 6214 нужно воспринять как группу $\odot 6214$ , группу 963 — как $\odot 963$ , 8272 — как $\odot 8272$ , 251 — как $\odot 251$ и как другой $\odot$ как группу $\odot 0$