反向因子

Question

好吧,我们都知道如果N给出它很容易计算N!.但反过来呢？

N!给出了你即将找到N - 这可能吗？我很好奇.

Answer 1

1. 设置X=1.
2. 生成 F=X!
3. F =输入吗？如果是,X则为N.
4. 如果没有,则设置X=X+1,然后再次从#2开始.

您可以使用以前的结果来优化F以计算new F(new F = new X * old F).

它的速度与反方向一样快,如果不是更快,因为除法通常比乘法更长.除了A之外,给定的因子A!保证所有整数都小于A因子,所以你花费的时间与计算运行因子一样多.

Answer 2

如果你有Q = N!在二进制中,计算尾随零.叫这个号码J.

如果N是2K或2K + 1,那么J等于2K减去2K的二进制表示中的1的数量,所以反复加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 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(如果存在的话).注意我们有帽子!≈e^(n ln n - n)(这是斯特林的近似值),所以你大致知道在哪里看.

问题当然是,很少有数字是阶乘; 所以你的问题只适用于一小部分输入.如果您的输入很小(例如,适合32位或64位整数),查找表将是最佳解决方案.

(你当然可以考虑反转Gamma函数的更普遍的问题.再次,二进制搜索可能是最好的方式,而不是解析的东西.我很高兴在这里显示错误.)

编辑:其实,在你不知道肯定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)

例如,您可以使用哈希表来实现它,或者如果您使用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\n

由于大整数运算的开销，计算阶乘的简单方法会太慢。相反，我们可以注意到，当 N \xe2\x89\xa5 7 时，每个阶乘可以通过其长度（即位数）唯一标识。

\n\n

\n
• 整数 x 的长度可以计算为 log10(x) + 1。
\n
• 对数乘积规则：log(a*b) = log(a) + log(b)
\n

\n\n

通过以上两个事实，我们可以说长度为N！是：

\n\n

\n\n

可以通过简单地添加 log10(i) 直到获得输入数字的长度来计算，因为 log(1*2*3*...*n) = log(1) + log(2) + log(3) + ... + log(n)。

\n\n

这段 C++ 代码应该可以解决问题：

\n\n

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

\n\n

（记得检查 n<7 的情况（基本阶乘计算应该没问题））

\n\n

完整代码： https: //pastebin.com/9EVP7uJM

\n