Антифакториал

[PAV]

Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее. Если на каком-то шаге пришли к 1 - значит, имеем факториал и сразу определили, для какого числа это факториал. А если на некотором шаге не 1, но на очередное число нацело не делится - значит, не факториал.

[Бодигрим]

Цитата:

Касательно формулы Стирлинга (которая оценивает с двух сторон), для больших чисел она дает довольно неплохую точность.

Неплохую _относительную_ точность.

Цитата:

Причем, по-моему, достаточно подставлять предполагаемые ответы в границы оценочного интервала

А откуда у вас возьмется некий оценочный интервал для _обращения_ формулы Стирлинга?

PAV, именно это выше предложил Sergei Suvorov.

Добавлено спустя 5 минут 55 секунд:

Spook писал(а):

Бодигрим под бинарными Вы имеете ввиду обычные x86 совместимые? И что значит $ord_2 N$?

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

$ord_2 x$ - это наибольшая степень 2, которая все еще делит $x$ нацело.

Spook писал(а):

Sergei Suvorov у Вас вроде как тоже перебор и скорее всего потребуется вводить длинные числа.

В алгоритме перебора только одно условие завершения - превышение текущим найденным факториалом заданного числа. А в алгоритме Sergei Suvorov есть возможность предварительного завершения, если на каком-то из шагов не разделилось нацело. Поэтому он будет выполняться куда быстрее.

Spook писал(а):

Мне тут удалось узнать еще такой вариант для случая не совсем больших чисел, который знакомые как-то раз применили на ACM: просто посчитали заранее и загнали в таблицу, а потом оттуда брали.

Ну, это уже не в кассу.

[Spook]

Бодигрим писал(а):

А откуда у вас возьмется некий оценочный интервал для _обращения_ формулы Стирлинга?

Я вот про какую формулу:
$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$

[Бодигрим]

И? Как вы применяете эту формулу для решения поставленной задачи?

[Spook]

Я думал подставлять числа $n$ и сравнивать со значением факториала. Из тех $n$, которые подойдут, потом можно непосредственно выбрать нужное. Вот такой был мой план.

Касательно идеи с нулями, Вы не получали зависимости пяти последовательных чисел от количества нулей? Я пока ее проследить не смог, как-то хитро эти нули добавляются.

[Бодигрим]

Spook писал(а):

Я думал подставлять числа $n$ и сравнивать со значением факториала. Из тех $n$, которые подойдут, потом можно непосредственно выбрать нужное. Вот такой был мой план.

Вам пришлось бы вычислять левую и правую части, которые являются достаточно сложными выражениями, на каждом шаге. Куда экономичнее просто перебирать последовательные факториалы - это всего одно умножение на каждом шаге.

Spook писал(а):

Касательно идеи с нулями, Вы не получали зависимости пяти последовательных чисел от количества нулей? Я пока ее проследить не смог, как-то хитро эти нули добавляются.

Как известно, количество нулей, на которое заканчивается $n!$, есть $ord_5 n! = \sum_{k=1}^\infty \lfloor n/5^k \rfloor$. Не следует пугаться последней суммы - на самом деле все ее члены, за исключением конечного их числа, суть нули. Кроме того отметим, что $\sum_{k=1}^\infty \lfloor n/5^k \rfloor < \sum_{k=1}^\infty n/5^k = n/4 $. C другой стороны

$$\sum_{k=1}^\infty \lfloor n/5^k \rfloor > \sum_{k=1}^{\log_5 n} (n/5^k-1) = {n(1-1/5^{\lfloor \log_5 n \rfloor})\over 4} -\lfloor \log_5 n \rfloor > (n-5)/4 - \log_5 n. $$

[Алексей К.]

PAV писал(а):

Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее.
В отъезде с... по ....

Похоже, не хотят ребята попроще... Хорошего отъезда!

[Echo-Off]

Spook писал(а):

$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$

$2\pi n$ под корнем должно быть

[Cave]

Факториал интересен тем, что для вычисления его значения в точке $n$ нужно его значение в точке $n-1$. Поэтому даже если у нас есть гипотеза, что число $n$ - антифакториал заданного числа $N$, то нам всё равно надо будет проверить её тем, что посчитать $n!$.
Поэтому мне простейшим представляется следующее решение: пока $n! < N$ увеличиваем $n$ на один и считаем новый факториал умножением на одно короткое число. По окончании цикла проверяем равенство $n! == N$ и получаем ответ.
По сложности, вроде, минимальные затраты, и элементарен в написании - нужно только умножение длинного числа на короткое.

[PAV]

Представление в компьютере больших целых чисел все равно надо будет делать в двоичном виде. В этом формате достаточно элементарно и быстро определяется число нулей, на которые оканчивается число, т.е. макисмальная степень двойки. Для числа $n!$ эта степень равна $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor + \lfloor\frac{n}{8}\rfloor + \cdots$, где $\lfloor\cdot\rfloor$ обозначают целую часть числа снизу.

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.

Если дело дойдет до проверки, то можно провести сокращение проверяемого большого числа на все степени двойки (в двоичном представлении это делается обычными сдвигами) и при вычислении факториала также сразу сокращать множители на все степени двойки. Это в какой-то степени укоротит длину чисел и ускорит выполнение умножений.

[juna]

PAV писал(а):

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$.

Эта оценка ошибочна.

[PAV]

Да, действительно. Должно быть от $n-\log_2 n$ до $n$, если я снова не ошибся.

[Батороев]

Spook писал(а):

1. Определить, является ли заданное число факториалом.

"Инженерный калькулятор Плюс" моего компьютера за 9 мин. подсчитал
$ 200000! = 1,4202253454703144049669463336823...e+973350 $, т.е. число имеет $ 973350 $ знаков.
Неужели, Вы оперируете более высокими величинами?

Если Вас вопрос интересует теоретически, то в принципе, для первой прикидки можно проверить делится ли без остатка заданное число, например, на тот же $ 200000! $

p.s. Кстати, в соседней теме Вы спрашивали, как можно проверить число на простоту?
Так вот, при помощи указанного выше факториала можно проверить все числа от $ 200000$ до $600000$.
Если данный факториал имеет остаток по модулю заданного числа, отличный от нуля, то это число - простое.
Если Вы отдельно введете проверку, делится ли число на $3$, то диапазон можно увеличить до $ 1000000$ и т.д.

[ewert]

PAV писал(а):

Представление в компьютере больших целых чисел все равно надо будет делать в двоичном виде. В этом формате достаточно элементарно и быстро определяется число нулей, на которые оканчивается число, т.е. макисмальная степень двойки. Для числа $n!$ эта степень равна $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor + \lfloor\frac{n}{8}\rfloor + \cdots$, где $\lfloor\cdot\rfloor$ обозначают целую часть числа снизу.

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.

Если дело дойдет до проверки, то можно провести сокращение проверяемого большого числа на все степени двойки (в двоичном представлении это делается обычными сдвигами) и при вычислении факториала также сразу сокращать множители на все степени двойки. Это в какой-то степени укоротит длину чисел и ускорит выполнение умножений.

Однако выгодно это только тогда, когда используется длинная арифметика, реализованная программным путём (т.к. реально в этом алгоритме требуется лишь аппаратная арифметика). И только для вычисления $N$ в случае, когда "$N!$" -- это действительно факториал. Для проверки же на факториальность всё равно понадобится та или иная последовательность делений.

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

[Spook]

Echo-Off писал(а):

Spook писал(а):

$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$

$2\pi n$ под корнем должно быть

Вы уверены? У меня в показателе степени стоит "

$$+\frac{1}{2}$$

"

Алексей К. писал(а):

PAV писал(а):

Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее.
В отъезде с... по ....

Похоже, не хотят ребята попроще... Хорошего отъезда!

Я, в общем, присоединяюсь, за исключением "нехотят" Думаю, в принципе, нужно
сделать как сказали PAV и Cave, вот только можно оптимизировать, напрмер, посчитать кол-во цифр и начать делить(умножать) не с 2, а с большего числа.

Бодигрим, да, пожалуй Стирлинг тут не лучший способ. Вариант с количеством нулей я все-таки на досуге попробую проверить. За неравенства спасибо, думаю, смогу получить точное выражение.

Батороев писал(а):

Неужели, Вы оперируете более высокими величинами?

Ну это просто задачка по программированию, в принципе, вряд ли числа будут больше.

Батороев писал(а):

p.s. Кстати, в соседней теме Вы спрашивали, как можно проверить число на простоту?
Так вот, при помощи указанного выше факториала можно проверить все числа от $ 200000$ до $600000$.
Если данный факториал имеет остаток по модулю заданного числа, отличный от нуля, то это число - простое.
Если Вы отдельно введете проверку, делится ли число на $3$, то диапазон можно увеличить до $ 1000000$ и т.д.

Интересная идея, оценить бы временную сложность и объем памяти.

PAV писал(а):

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.

В принципе получается, что мы вибираем меньшего кандидата и все-таки считаем полностью его факториал?

ewert писал(а):

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

Вы имеете ввиду просто последовательное деление?