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

[Spook]

Две независимые задачи.

1. Определить, является ли заданное число факториалом.
2. Требуется по факториалу найти исходное число.

[ИСН]

Решение перебором столь ненамного длиннее самого условия задачи, что и говорить не о чем.

[Spook]

Хм... Думал, в качестве альтернативы, может как-нибудь через формулу Стирлинга, например.

[Бодигрим]

Можно, конечно, приблизительно обратить формулу Стирлинга, получить приближенный "антифакториал" и попробовать подставить числа в пределах погрешности. Но это достаточно трудоемкая операция ИМХО: даже в простейшем случае надо разрешать уравнение вида $n(\ln n-1)+{1\over2}\ln n = {\rm const}$, применяя численные методы.

Я бы сделал иначе: подсчитал бы число нулей, на которое заканчивается проверяемое число. По числу нулей однозначно выяснил бы (не то, чтобы это было совсем просто, но...) возможное значение антифакториала с погрешностью $\pm2$ и проверил бы эти числа.

[Евгений Б.]

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

Я не до конца правда эту идею продумал. Подумаю ещё может что и выйдет из этого (или не выйдет).

[Бодигрим]

Цитата:

Я не до конца правда эту идею продумал.

Ваша идея, по-видимому, потребует полного разложения на множители. Эта задача является весьма трудоемкой и для проверки числа $n$ потребует $O(\sqrt n)$ шагов. В то же время простой перебор факториалов, не превосходящих $N$, продлится не более $O(\ln n)$.

[juna]

Отсеивать числа, не являющиеся факториалом, можно.
У факториала степень двойки определяется:
$ord_2N!=\sum\limits_{i=1}^{\lfloor\frac{\ln N}{ln 2}\rfloor}\lfloor \frac{N}{2^i}\rfloor$,
степень тройки:
$ord_3N!=\sum\limits_{i=1}^{\lfloor\frac{\ln N}{ln 3}\rfloor}\lfloor \frac{N}{3^i}\rfloor$.
Причем, порядок двойки мало отличается от самого $N$.

[Евгений Б.]

Цитата:

Эта задача является весьма трудоемкой

Ну Я ответил что первое пришло на ум.

А вот ещё идея:

для случая когда число больше трёх
делим целочисленно на два наше число и проверяем
если произведение (число/2) * (число/2 -1)> число то
делим ещё раз и так далее
а если меньше значит у нас появится возможный промежуток, в котором искомый ответ задачи.

этот алгоритм возможно не полно описан я его ещё не протестировал хорошенько
может что не учёл тут

[Бодигрим]

Цитата:

Отсеивать числа, не являющиеся факториалом, можно.

Вообщем-то, мое предложение считать нули в десятичной системе счисления эквивалентно подсчету ${\rm ord}_5 n!$.

Цитата:

для случая когда число больше трёх
делим целочисленно на два наше число и проверяем
если произведение (число/2) * (число/2 -1)> число то
делим ещё раз и так далее
а если меньше значит у нас появится возможный промежуток, в котором искомый ответ задачи.

Что-то я не уловил. Неравенство $\lfloor n/2 \rfloor\lfloor n/2 -1\rfloor > n $ верно при всех $n\ge8$.

[Евгений Б.]

Цитата:

Неравенство $\lfloor n/2 \rfloor\lfloor n/2 -1\rfloor > n $ верно при всех $n\ge8$.

Да, действительно.
Тогда наверное нужно с увеличением числа увеличивать и делитель.
А насколько велико число можно по степени 10, например судить.

[Бодигрим]

Цитата:

Тогда наверное нужно с увеличением числа увеличивать и делитель.

Вы не могли бы разъяснить предлагаемый вами алгоритм подробнее? Я не понимал, чего вы добиваетесь, деля на 2, а теперь и вовсе потерял нить рассуждений.

[Sergei Suvorov]

Можно воспользоваться итерационной формулой

x_n = x_n_-_1/n

x_1 - это число, которое мы проверяем. На каждом шаге:
1. Если x_n = n+1, то x_1 = x_n!.
2. Если не делится без остатка, то х_1 не является факториалом.

Прошу прощения за столь вольное изложение:).

[juna]

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

Вообщем-то, мое предложение считать нули в десятичной системе счисления эквивалентно подсчету ${\rm ord}_5 n!$.

Дело в том, что ${\rm ord_2 N!}<N$ и мало от него отличается при относительно небольших $N$ (а для практических расчетов и совсем мало). Соответственно, зная порядок $N$, используем степень тройки уже как проверочную.

[Бодигрим]

Вообще при практической реализации ИМХО тут главная задача - как можно быстрее уйти от "длинной арифметики" или по крайней мере сделать вычисления как можно более простыми с точки зрения используемого технического обеспечения. В этом плане прямой перебор плох, алгоритм Sergei Suvorov'а несколько лучше (правда он использует деление, которое более трудоемко, чем умножение)... Для бинарных компьютеров, наверное, в качестве первой проверки действительно стоит подсчитать $ord_2 N!$... Короче, это уже вопросы реализации.

[Spook]

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

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

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

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

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