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

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

int inverse_factorial(int factorial){
    int current = 1;
    while (factorial > current) {
        if (factorial % current) {
            return -1; //not divisible
        }
        factorial /= current;
        ++current;
    }
    if (current == factorial) {
        return current;
    }
    return -1;
}

Да. Назовем ваш вход x. Для малых значений x вы можете просто попробовать все значения n и посмотреть, есть ли n! = х. Для большего x вы можете выполнить двоичный поиск по n, чтобы найти правильное n (если оно существует). Обратите внимание, что у нас есть n! ≈ e ^ (n ln n - n) (это приближение Стирлинга ), так что вы примерно знаете, где искать.

Проблема, конечно, в том, что очень немногие числа являются факториалами; поэтому ваш вопрос имеет смысл только для небольшого набора входных данных. Если ваш ввод небольшой (например, подходит для 32-битного или 64-битного целого числа), таблица поиска будет лучшим решением.

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

Редактировать : На самом деле, в случае, если вы не знаете наверняка, что x является факториальным числом, вы можете не получить столько (или что-то еще) с помощью двоичного поиска с использованием приближения Стирлинга или Гамма-функция над простыми решениями. Обратный факториал растет медленнее, чем логарифмический (это потому, что факториал суперэкспоненциальный), и вам нужно выполнять арифметические действия произвольной точности, чтобы найти факториалы и все равно умножить эти числа.

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

Несколько способов. Используйте таблицы поиска, используйте двоичный поиск, используйте линейный поиск ...

Таблицы поиска очевидны:

for (i = 0; i < MAX; ++i)
    Lookup[i!] = i; // you can calculate i! incrementally in O(1)

Вы можете реализовать это, используя хеш-таблицы , например, или если вы используйте C ++ / C # / Java, у них есть свои контейнеры, похожие на хэш-таблицы.

Это полезно, если вам приходится делать это много раз, и каждый раз это должно быть быстро, но вы можете позволить себе потратить некоторое время на создание этой таблицы.

Двоичный поиск : предположим, что число m = (1 + N!) / 2 . Есть м! больше, чем N! ? Если да, сократите поиск от 1 до м! , в противном случае уменьшите его до м! + 1 и N! . Рекурсивно применяйте эту логику.

Конечно, эти числа могут быть очень большими, и вы можете в конечном итоге выполнить множество нежелательных операций. Лучше всего выполнить поиск между 1 и sqrt (N!) , используя двоичный поиск, или попытаться найти еще лучшие приближения, хотя это может быть нелегко. Рассмотрите возможность изучения гамма-функции .

Линейный поиск : Пожалуй, лучший в данном случае. Вычислите 1 * 2 * 3 * ... * k , пока произведение не станет равным N! и вывод k .

inverse_factorial( X )
{
   X_LOCAL = X;
   ANSWER = 1;
   while(1){
      if(X_LOCAL / ANSWER == 1)
        return ANSWER;
       X_LOCAL = X_LOCAL / ANSWER;
       ANSWER = ANSWER + 1;
    }
}

Если у вас Q = N! в двоичном формате считать нули в конце. Назовите этот номер J.

Если N равно 2K или 2K + 1, то J равно 2K минус количество единиц в двоичном представлении 2K, поэтому добавляйте 1 снова и снова, пока количество единиц, которые вы добавили, не станет равным количеству 1 в результате.

Теперь вы знаете 2К, а N равно 2К или 2К + 1. Чтобы определить, какой именно, посчитайте множители наибольшего простого числа (или любого другого простого числа, на самом деле) в 2K + 1 и используйте это для проверки Q = (2K + 1) !.

Например, предположим, что Q (в двоичном формате) равно

1111001110111010100100110000101011001111100000110110000000000000000000

(Извините, он такой маленький, но у меня нет инструментов для работы с большими числами.)

Есть 19 нулей в конце, то есть

10011

Теперь увеличиваем:

1: 10100
2: 10101
3: 10110 bingo!

Итак, N равно 22 или 23. Мне нужен простой множитель 23, и, ну, я должен выбрать 23 (бывает, что 2K + 1 простое число, но я этого не планировал, и это не так. не нужно). Итак, 23 ^ 1 должно делить 23 !, оно не делит Q, поэтому

N=22

1. Установить X = 1 .
2. Создать F = X!
3. F = вход? Если да, то X равно N.
4. Если нет, то установите X = X + 1 , затем снова начните с # 2.

Вы можете оптимизировать, используя предыдущий результат F для вычисления нового F ( новый F = новый X * старый F ).

Это так же быстро, как и движение в обратном направлении, если не быстрее, учитывая, что деление обычно занимает больше времени, чем умножение. Данный факториал A! гарантированно будет иметь все целые числа меньше, чем A в качестве факторов в дополнение к A, так что вы потратите столько же времени на их разложение, как на просто вычисление текущего факториала.

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

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

Хорошо, если вы знаете , что M на самом деле является факториалом некоторого целого числа, тогда вы можете использовать

n! = Gamma(n+1) = sqrt(2*PI) * exp(-n) * n^(n+1/2) + O(n^(-1/2))

Вы можете решить это (или, на самом деле, решить ln (n!) = Ln Gamma (n + 1) ) и найдите ближайшее целое число. Оно по-прежнему является нелинейным, но вы можете легко получить приближенное решение с помощью итераций (на самом деле, я ожидаю, что коэффициент n ^ (n + 1/2) будет равен достаточно).