задача о факториалах ...

[Джек]

Найти количество цыфр у числе $n!$,$n\leq1000000$.

Пример:Ввод 7......Вывод 4....

[Nerazumovskiy]

мне кажется эта задача для математического раздела

[luitzen]

Может, просто сложить десятичные логарифмы множителей?
Ну или натуральные (если так проще), а потом всё поделить на натуральный логарифм десяти.

У меня браузер число разрядов в факториале миллиона за секунду высчитывает.
Хрен ли там ещё оптимизировать…

function digits (base) {
var natural = 0;
   for (var i = base; i>0; i--) {
   natural += Math.log(i);
   }
return natural / Math.LN10;
}

[Dandan]

\sqrt{2\pi n}\left(\frac{n}{e}\right)^n < n! < \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n)} (из формулы Стирлинга)

[Nerazumovskiy]

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

[Dandan]

а нам не нужно считать сам факториал, нам нужно лищь количество цифр. Разница log_{10}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n)} -log_{10}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n = {1/(12n)}log_{10}e достаточно мала. Проблемы будут только если целое число попадёт в этот промежуток. Тогда ответ либо это попавшее число, либо на единицу меньше. Как абсолютно точно подсчитать пока не знаю. Может тут лучше приближение найти можно http://mathworld.wolfram.com/StirlingsA ... ation.html

[luitzen]

Кстати, желает кто-нибудь привести пример достаточно большого $n$ такого, что $\left\lceil\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \right\rceil$ и $\left\lfloor \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n }e^{1/(12n)}\right\rfloor$ имеют разное число знаков в десятичной записи? Ну или доказать, что такого $n$ нет…

[Nerazumovskiy]

так небудет такой&

[worm2]

luitzen в сообщении #187458 писал(а):

Ну или доказать, что такого $n$ нет…

Скорее всего, найдётся даже бесконечное число таких $n$.
Исхожу из вероятностных соображений.
Интересующий нас интервал логарифмов убывает с ростом $n$ как $O(1/n)$. Если его "проекцию" на отрезок [0,1] рассматривать, как случайную, то она бесконечное число раз покроет любую точку отрезка, т.к. ряд с общим членом $1/n$ расходится.
Извините за сумбур. Не могу сформулировать мысль одновременно кратко и однозначно. Надеюсь, что понятно и так

[ewert]

luitzen писал(а):

Кстати, желает кто-нибудь привести пример достаточно большого $n$ такого, что $\left\lceil\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \right\rceil$ и $\left\lfloor \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n }e^{1/(12n)}\right\rfloor$ имеют разное число знаков в десятичной записи? Ну или доказать, что такого $n$ нет…

Опыт показывает, что пределах первого миллиона целые части десятичных логарифмов для точного факториала и для главного члена формулы Стирлинга совпадают. И вообще: минимальные дробные части $\lg n!$ с ростом $n$, конечно, уменьшаются, но вот минимальные отношения дробной части $\lg n!$ к поправке $(12n\ln10)^{-1}$, наоборот, уверенно растут, хотя и очень медленно. Наверняка есть на этот счёт какая-нибудь теорема -- но не у меня, естественно.

[ha]

Тут компьютер мне шепчет, что, не считая n=1, первые контрпримеры это 3121515, 4187665, 4423458,....

[Лиля]

Воспользуйся апроксимацией Рамануяна
$\log n! \approx n\log n - n + \frac {\log(n(1+4n(1+2n)))} {6} + \frac {\log(\pi)} {2}.$

[Nerazumovskiy]

а помойму все гораздо проще:)
считаем суму логарифмов от $0$ до $n$ потом преобразовем этот логарифм к 10-тичному основанию и прибавляем 1, вот и ответ)

[worm2]

Nerazumovskiy, Вы чуть опоздали

[Nerazumovskiy]

worm2 писал(а):

luitzen в сообщении #187458 писал(а):

Ну или доказать, что такого $n$ нет…

Скорее всего, найдётся даже бесконечное число таких $n$.
Исхожу из вероятностных соображений.
Интересующий нас интервал логарифмов убывает с ростом $n$ как $O(1/n)$. Если его "проекцию" на отрезок [0,1] рассматривать, как случайную, то она бесконечное число раз покроет любую точку отрезка, т.к. ряд с общим членом $1/n$ расходится.
Извините за сумбур. Не могу сформулировать мысль одновременно кратко и однозначно. Надеюсь, что понятно и так

если в этом сообщении вы сакзали тоже что и я, то мисль была сверх краткой