Обратный факториал

Question

Ну, мы все знаем, что если дано N, то легко вычислить N !. Но как насчет обратного?

N! дается, и вы собираетесь найти N - это возможно? Мне любопытно.

Answer 1

int p = 1,i;
//assume variable fact_n has the value n!
for(i = 2; p <= fact_n; i++) p = p*i;
//i is the number you are looking for if p == fact_n else fact_n is not a factorial

Я знаю, что это не псевдокод, но его довольно легко понять

Answer 2

На основании:

Полный инвертированный факториал, действительный для x> 1

Используйте предложенный расчет. Если факториал можно выразить в полной двоичной форме, алгоритм имеет вид:

Предположим, что входные данные являются факториальными x, x = n!

1. Возврат 1 для 1
2. Найдите число конечных 0 в двоичном разложении факториала x, отметим его t
3. Рассчитать x / fact (t), x, деленное на факториал t, математически x / (t!)
4. Найдите, сколько раз x / fact (t) делит t + 1, округленное до ближайшего целого числа, обозначим его m
5. Возврат m + t

__uint128_t  factorial(int  n);

int invert_factorial(__uint128_t fact)
{
    if (fact == 1) return 1;

    int t = __builtin_ffs(fact)-1;
    int res = fact/factorial(t);

    return t + (int)log(res)/log(t+1);
}

128-бит уступает 34!

Answer 3

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

Что более интересно, так это построение обратной функции Гамма, которая расширяет факториальную функцию до положительных действительных чисел (и даже для большинства комплексных чисел). Оказывается, построение обратного является сложной задачей. Тем не менее, это было решено явно для большинства положительных действительных чисел в 2012 году в следующей статье: http://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002-9939-2011-11023-2.pdf. Явная формула приведена в следствии 6 в конце статьи.

Обратите внимание, что он включает в себя интеграл в бесконечной области, но при тщательном анализе я считаю, что разумная реализация может быть построена. Лучше ли это, чем простая схема последовательного приближения на практике, я не знаю.

Answer 4

Просто разделите на положительные числа, то есть: 5! = 120 - >> 120/2 = 60 || 60/3 = 20 || 20/4 = 5 || 5/5 = 1

Таким образом, последнее число перед результатом = 1 является вашим числом.

В коде вы можете сделать следующее:

number = res
for x=2;res==x;x++{
    res = res/x

} 

или что-то в этом роде. Этот расчет нуждается в улучшении для неточных чисел.

Answer 5

C / C ++ код для what the factorial (r - получающийся факториал):

int wtf(int r) {
    int f = 1;

    while (r > 1)
        r /= ++f;

    return f;
}

Образцы тестов:

Call: wtf(1)
Output: 1

Call: wtf(120)
Output: 5

Call: wtf(3628800)
Output: 10

Answer 6

In C из моего приложения Расширенный калькулятор тригонометрии v1.6.8

    double arcfact(double f) {
        double i=1,result=f;
        while((result/(i+1))>=1) {
            result=result/i;
            i++;
        }
        return result;
    }

Что вы думаете об этом? Работает корректно для целых чисел факториалов.

Answer 7

Если вы не знаете , является ли число M N! или нет, достойным тестом является проверка, делится ли оно на все маленькие простые числа, пока приближение Стерлинга этого простого числа не станет большечем M.В качестве альтернативы, если у вас есть таблица факториалов, но она недостаточно высока, вы можете выбрать самый большой факториал в своей таблице и убедиться, что M делится на это.