如何有效計算階乘 T2 項中質數「i」的指數，其中 exponent(i) = sum(j=1,2,3,4,5,...) of (4N/( i^j))

如何有效計算階乘 T2 項中質數「i」的指數，其中 exponent(i) = sum(j=1,2,3,4,5,...) of (4N/( i^j)) - (2N/(i^j))？

Mary-Kate Olsen

發布： 2024-12-05 16:19:11

原創

836 人瀏覽過

How can I efficiently compute the exponent of a prime `i` in the T2 term of a factorial, where exponent(i) = sum(j=1,2,3,4,5,...) of (4N/(i^j)) - (2N/(i^j))?

問題中的問題是找到一種快速方法來計算快速精確 bigint 階乘表達式中的 T2 項。 T2 項定義為：

T2(4N) = multiplication(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

登入後複製

這已經相當快了，並且透過一些程式技巧，複雜性接近 ~ O(log(n))。

要清楚的是，我的目前的實作是這樣的：

longnum fact(const DWORD &amp;x,longnum &amp;h) // h return (x>>1)! to speed up computation
    {
    if (x==0) { h=1; return  1; }
    if (x==1) { h=1; return  1; }
    if (x==2) { h=1; return  2; }
    if (x==3) { h=1; return  6; }
    if (x==4) { h=2; return 24; }
    int N4,N2,N,i; longnum c,q;
    N=(x>>2);
    N2=N<<1;
    N4=N<<2;
    h=fact(N2,q);                                          // get 2N! and N!
    c=h*h; for (i=(N2+1)|1;i<=N4;i+=2) c*=i; c/=q;         // c= ((2N)!).((2N)!)/ N!
    for (i=N4+1;i<=x;i++) c*=i; c.round(); c<<=N  ;        // convert 4N! -> x!, cut off precision losses
    for (i=(N2+1)|1,N2=x>>1;i<=N2;i++) h*=i; h.round();    // convert 2N! -> (x/2)!, cut off precision losses
    return c;
    }

登入後複製

longnum fact(const DWORD &x)

{
longnum tmp;
return fact(x,tmp);
}

登入後複製

Now my question:

Is there a fast way to obtain N! from this T2 **term**:

登入後複製

T2 = (4N)！ / (((2N)!).((2N)!))

so:

登入後複製

(4N)！ = (((2N)!).((2N)!)).T2

This would help a lot because then it would not be needed to compute .../(N!) for factorial. 

The T2 term is always integer-decomposable to this:

登入後複製

T2 = T2 * N!

Finally, it hit me :) I have done a little program for primes decomposition of factorials and then suddenly all becomes much clearer:

登入後複製

4！ = 2!.2!.(2^1).(3^1) = 24
8！ = 4!.4!.(2^1).(5^1).(7^1) = 40320
12！ = 6!.6!.(2^2).(3^1).(7^1).(11^1) = 479001600
16！ = 8!.8!.(2^1).(3^2).(5^1).(11^1).(13^1) = 20922789888000
20！ = 10!.10!.(2^2).(11^1).(13^1).(17^1).(19^1) = 2432902008176640000
24！ = 12!.12!.(2^2).(7^1).(13^1).(17^1).(19^1).(23^1) = 620448401733239439360000
28！ = 14!.14!.(2^3).(3^3).(5^2).(17^1).(19^1).(23^1) = 304888344611713860501504000000
32！ = 16!.16!.(2^1).(3^2).(5^1).(17^1).(19^1).(23^1).(29^1).( 31^1) = 263130836933693530167218012160000000
36！ = 18!.18!.(2^2).(3^1).(5^2).(7^1).(11^1).(19^1).(23^1).( 29^1).(31^1) = 37199332678990121746799944815083520000000
40！ = 20!.20!.(2^2).(3^2).(5^1).(7^1).(11^1).(13^1).(23^1).( 29^1).(31^1).(37^1) = 815915283247897734345611269596115894272000000000

After analyzing the prime exponents of the T2 term (the rest after half factorials ^ 2) I derive the formula for them:

登入後複製

T2(4N) = ( i ^ 的乘法(i=2,3,5,7,171) (4N/(i^j))-(2N/(i^j)) 的 sum(j=1,2,3,4,5,...)

The problem is that the divisions 4N/(i^j) and 2N/(i^j)  must be done in integer math so they cannot be simplified easily.

So I have another question:

How can I compute this: exponent(i) = sum(j=1,2,3,4,5,...) of (N/(i^j)) effectively?

登入後複製

以上是如何有效計算階乘 T2 項中質數「i」的指數，其中 exponent(i) = sum(j=1,2,3,4,5,...) of (4N/( i^j)) - (2N/(i^j))？的詳細內容。更多資訊請關注PHP中文網其他相關文章！