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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Теперь вы знаете 2K, а N равно 2K или 2K + 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

Answer 3

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;
}

Answer 4

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

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

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

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

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

Answer 5

Ну, если вы знаете , что 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)).

Answer 6

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

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

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

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

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

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

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

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

Answer 7

Если введенное число действительно N, его довольно просто вычислить N.

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

• Длина целого числа x может быть вычислена как log10 (x) + 1.
• Правило произведения логарифмов: log (a * b) = log (a) + log (b)

Используя два приведенных выше факта, мы можем сказать, что длина N! есть

, который можно вычислить, просто добавив log10 (i), пока мы не получим длину нашего входного числа, поскольку log (1 * 2 * 3 * ... * n) = log (1) + log (2) + log (3) + ... + log (n).

Этот код на C ++ должен помочь:

double result = 0;
for (int i = 1; i <= 1000000; ++i) {  // This should work for 1000000! (where inputNumber has 10^7 digits)
    result += log10(i);
    if ( (int)result + 1 == inputNumber.size() ) {    // assuming inputNumber is a string of N!
        std::cout << i << endl;
        break;
    }
}

(не забудьте проверить случаи, когда n <7 (базовый факторный расчет должен быть в порядке)) </p>

Полный код: https://pastebin.com/9EVP7uJM

Answer 8

Вот некоторый код clojure:

(defn- reverse-fact-help [n div]
    (cond (not (= 0 (rem n div))) nil
          (= 1 (quot n div)) div
          :else (reverse-fact-help (/ n div) (+ div 1))))
(defn reverse-fact [n] (reverse-fact-help n 2))

Предположим, что n = 120, div = 2. 120/2 = 60, 60/3 = 20, 20/4 = 5, 5/5 = 1, возврат 5

Предположим, что n = 12, div = 2. 12/2 = 6, 6/3 = 2, 2/4 = .5, возврат «ноль»

Answer 9

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;
    }
}

Answer 10

Эта функция основана на последовательных приближениях! Я создал его и реализовал в Advanced Trigonometry Calculator 1.7.0

double arcfact(double f){
 double result=0,precision=1000;
 int i=0;
 if(f>0){
   while(precision>1E-309){
     while(f>fact(result+precision)&&i<10){
 result=result+precision;
 i++;
   }
   precision=precision/10;
   i=0;
  }
  }
  else{
result=0;
   }
   return result;
 }