Факториал

[Ward]

Здравствуйте!

Может ли $n!$ оканчиваться ровно на 1971 нулей в десятичной записи?

Никак не могу решить. Подскажите пожалуйста.

[Aritaborian]

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

[Ward]

на 1 нуль может оканчиваться. Например $5!=120$
на 2 нуля тоже, на 3 и 4 тоже, но уже на 5 нулей он оканчиваться не может

[Aritaborian]

А на 6, 7, 8, 9, 10 нулей?

[Ward]

На 6, 7, 8, 9, 10 нулей тоже может оканчиваться.
Например 25!, 30!, 35!, 40!, 45!

-- 31.01.2013, 04:45 --

вот на 11 нулей она оканчиваться не может.
Да и на 17 нулей оканчиваться не может

[jrock]

Можно придумать $z(n)$ которая перечисляет последовательность кол-ва возможных нулей.
Короче говоря, задача решается абсолютно в лоб: посмотрите на числа от которых может получится ноль, потом подумайте о минимальной информации, которая вам необходимо что бы это понять. Там явно должна быть какая-то цикличность.

[JMH]

(Оффтоп)

Ward в сообщении #678150 писал(а):

Может ли $n!$ оканчиваться ровно на 1971 нулей в десятичной записи?

Оцените минимальное колличество нулей, на которые оканчивается $(10^{1971})!$

Upd: Чёрт, невнимательно прочёл условие

[Евгений Машеров]

Может. 7895!, 7896!, 7897!, 7898! и 7899!. А вот на 1972 нулей - не может.

[Sonic86]

Ward, Вам решение в общем виде хоть понятно? Есть достаточно компактная формула для числа нулей $n!$

[Ward]

Может такая формула.
двойка входит в $n!$ с показателем

$$\left[\frac{n}{2}\right]+\left[\frac{n}{2^2}\right]+\dots=a,$$

а пятерка с показателем

$$\left[\frac{n}{5}\right]+\left[\frac{n}{5^2}\right]+\dots=b$$

Так как $a\geqslant b$, то количество нулей в десятичной записи $n!$ равно $b$
Или не так?

[Sonic86]

Ну значит поняли.

Вообще, была вот такая тема, там есть точный критерий относительно числа нулей в произвольной системе счисления. Но если надо быстро и только для десятичной системы счисления, можно сделать проще: поскольку число нулей - неубывающая функция от $n$, то просто берем $n$ с меньшим и с бОльшим числом нулей и далее ищем двоичным поиском искомые значения.

[Ward]

Sonic86 в сообщении #678463 писал(а):

то просто берем $n$ с меньшим и с бОльшим числом нулей и далее ищем двоичным поиском искомые значения.

Вообще не понял. Можете объяснить на примере?

-- 31.01.2013, 20:42 --

В той же теме число разлагается по системе $u_s=\dfrac{p^{s+1}-1}{p-1}$, а у нас система десятичная ведь

-- 31.01.2013, 21:14 --

Sonic86
Вообще моя задача сводится к такой: существует ли такое $n$, что

$$\left[\frac{n}{5}\right]+\left[\frac{n}{5^2}\right]+\dots=1971$$

[Евгений Машеров]

Именно так. Для получения начального приближения убираем "целую часть" и находим сумму геометрической прогрессии. Что даёт начальное значение для n, которое проверяем. Скорее всего не подходит, и проверяем ближайшие.

[Whitaker]

Число нулей, которым оканчивается $n!$ совпадает с показателем, с которым 5 входит в разложение $n!$ на простые множители.
Нам нужно найти такое число $n$, что $v_5(n!)=1971$
Разложим число $n$ по пятеричной системе и получаем выражение:

$$n=a_k5^k+a_{k-1}5^{k-1}+\dots+5a_1+a_0,$$

где $a_0, a_1, \dots, a_k \in \{0, 1, 2, 3, 4\}$.
Так как $v_5(n!)=\sum \limits_{j\geqslant 1}\left[\dfrac{n}{5^j}\right]$
Для $j: 1\leqslant j\leqslant k$ имеем, что $\left[\dfrac{n}{5^j}\right]=a_k5^{k-j}+a_{k-1}5^{k-1-j}+\dots+a_j$
Тогда

$$\sum \limits_{j\geqslant 1}\left[\dfrac{n}{5^j}\right]=(a_k5^{k-1}+\dots+a_1)+(a_k5^{k-2}+\dots+a_2)+\dots+(a_k5+a_{k-1})+a_k=$$

$$=a_k\frac{5^k-1}{4}+\dots+a_2\frac{5^2-1}{4}+a_1\frac{5-1}{4}=1971$$

Отсюда получаем, что:

$$a_k(5^k-1)+a_2(5^2-1)+a_1(5-1)=1971\times 4=7884$$

Ну отсюда нетрудно выяснить, что $a_j=0$ при $j>5$ и $a_5=2, a_4=2, a_3=3, a_4=0, a_5=4$ и $n=2\times 5^5+2\times 5^4+3\times 5^3+0\times 5^2+4\times 5^1+a_0=7895+a_0$, где $a_0\in \{0, 1, 2, 3, 4\}$
Значит, $n\in \{7895, 7896, 7897, 7898, 7899\}$