2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 задача о факториалах ...
Сообщение18.02.2009, 14:11 
Найти количество цыфр у числе $n!$,$n\leq1000000$.

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

 
 
 
 
Сообщение18.02.2009, 16:38 
мне кажется эта задача для математического раздела

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

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

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

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

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

 
 
 
 
Сообщение18.02.2009, 17:49 
а нам не нужно считать сам факториал, нам нужно лищь количество цифр. Разница 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

 
 
 
 
Сообщение18.02.2009, 19:27 
Кстати, желает кто-нибудь привести пример достаточно большого $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$ нет…

 
 
 
 
Сообщение18.02.2009, 20:22 
так небудет такой&

 
 
 
 
Сообщение18.02.2009, 20:43 
Аватара пользователя
luitzen в сообщении #187458 писал(а):
Ну или доказать, что такого $n$ нет…

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

 
 
 
 
Сообщение19.02.2009, 15:02 
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}$, наоборот, уверенно растут, хотя и очень медленно. Наверняка есть на этот счёт какая-нибудь теорема -- но не у меня, естественно.

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

 
 
 
 
Сообщение25.02.2009, 03:50 
Аватара пользователя
Воспользуйся апроксимацией Рамануяна
$\log n! \approx n\log n - n + \frac {\log(n(1+4n(1+2n)))} {6} + \frac {\log(\pi)} {2}.$

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

 
 
 
 
Сообщение04.03.2009, 19:27 
Аватара пользователя
Nerazumovskiy, Вы чуть опоздали :)

 
 
 
 
Сообщение05.03.2009, 17:12 
worm2 писал(а):
luitzen в сообщении #187458 писал(а):
Ну или доказать, что такого $n$ нет…

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

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group