Reverse factorial

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的整数都是除A以外的因子，因此您只需花费尽可能多的时间分解这些因子，就像计算运行因子一样。

Answer 2

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 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。对于x的小值，你可以尝试n的所有值，看看n！ = x。对于较大的x，可以在n上进行二分搜索以找到正确的n（如果存在）。请注意我们有n！ ≈e ^（n ln n - n）（这是Stirling's approximation），所以你大概知道在哪里看。

问题当然是很少有数字是阶乘因子;所以你的问题只适用于一小部分输入。如果您的输入很小（例如适合32位或64位整数），查找表就是最好的解决方案。

（你当然可以考虑颠倒Gamma function的更一般的问题。同样，二进制搜索可能会是最好的方式，而不是一些分析。我很乐意在这里是错误显示。）

编辑：实际上，如果您不确定x是否是阶乘数，那么使用斯特林逼近或伽玛函数进行二分搜索时，您可能无法获得所有这些（或任何其他） 。逆阶乘增长慢于对数（这是因为阶乘是超指数），并且您必须执行任意精度算术来查找阶乘并将这些数字相乘。例如，参见Draco Ater的一个想法（当扩展到任意精度算法时）对所有x都适用的答案。甚至更简单，甚至更快，因为乘法比分裂更快，是Dav的答案，这是最自然的算法......这个问题是另一个简单的胜利，它似乎。:-)

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) 

您可以实现这一点使用hash tables例如，或者如果您使用C++/C＃/ Java，他们有自己的哈希表类容器。

这很有用，如果你不得不这样做很多次，每次都必须快，但你可以花一些时间建立这张表。

二进制搜索：假设编号为m = (1 + N!)/2。是m!大于N!？如果是，则减少1到m!之间的搜索，否则将其在m! + 1和N!之间减小。递归地应用这个逻辑。

当然，这些数字可能会非常大，你可能会做很多不需要的操作。更好的方法是使用二分搜索在1到sqrt(N!)之间搜索，或尝试找到更好的近似值，尽管这可能并不容易。考虑研究gamma function。

线性搜索：在这种情况下可能是最好的。计算1*2*3*...*k，直到产品等于N!并输出k。

Answer 7

如果不知道一些M是否N!与否，一个体面的测试是测试如果它是由所有的小素数整除，直到总理的斯特林近似比M大。另外，如果你有一个阶乘表，但它不够高，你可以选择表中最大的因子，并确保M可以被整除。

Answer 8

如果您有Q = N！在二进制中，计算尾随零。将此数字称为J.

如果N是2K或2K + 1，那么J等于2K减去2K的二进制表示中的1的数目，因此一次又一次地加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 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

检查反伽玛功能，这里http://functions.wolfram.com/GammaBetaErf/InverseGammaRegularized/ 他们有多个aproximations

Answer 11

下面是一些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 = 3.5， '零'

Answer 12

回报在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 13

此功能基于逐次逼近！我创建它，并在高级三角计算器实现它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; 
} 

Answer 14

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 15

简单地除以正数，即：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 16

大多数数字不在阶乘函数的输出范围内。如果这是您想要测试的内容，可以很容易地使用斯特林公式或目标数字的位数来近似，如其他人所述，然后执行二进制搜索以确定高于和低于给定数字的阶乘。

更有趣的是构造Gamma函数的反函数，该函数将阶乘函数扩展为正实数（以及最复杂的数字）。事实证明，构造逆是一个难题。然而，在下面的文章中，它在2012年被大多数正实数明确解决：http://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002-9939-2011-11023-2.pdf。本文末尾的推论6给出了明确的公式。

请注意，它涉及到无限域上的积分，但通过仔细分析，我相信可以构建一个合理的实现。在实践中，这是否比简单的逐次逼近方案更好，我不知道。

Answer 17

n！很容易因素。因此，除以2,3,5,7 ...并检查指数，你可以分多少次。

现在的问题是如果你有n！素数p的指数是什么？

首先，n！如果它是素数，则只能加n。

你每增加一个素数p或它的任何一个幂都在n之内。你会看到多少次p。那么它必须是针对

意味着

同样从黄金的权力

算法如下最大ķ。

假设我们有10888869450418352160768000000

我们可以将

2，分23次

3,13倍

5,6

7,3

11，2

13,2

17，1

23，1

不能整除29

这意味着，它是（23和29之间的数字通常的范围是多少较大，但这个例子仍然有用）。

现在我们可以在23和29之间使用二进制搜索来获得可被2,3整除的集合。请注意，只能有两个这样的数字。我们尝试26，轻松地发现，这是

如果这不会是这种情况，我们会继续在段23至26或26至29取决于结果。

所以它是26或27。我们对3和其他的做同样的事情，直到我们得到两个可能数字中的任何一个的匹配。这些数字对于至少一个给定的素数将会有不同的结果。

因此，如果上面的是一个阶乘它是27检查与上述相同为5,7,11,13,17,19和23的阶乘是表示一切都很好，它确实是27.