Wie kann ich den Exponenten einer Primzahl „i' im T2-Term einer Fakultät effizient berechnen, wobei Exponent(i) = Summe(j=1,2,3,4,5,...) von (4N/( i^j)) - (2N/(i^j))?

Das Problem in der Frage besteht darin, eine schnelle Möglichkeit zu finden, den T2-Term im Ausdruck für eine schnelle exakte Bigint-Fakultät zu berechnen. Der T2-Term ist definiert als:

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

Das geht schon ziemlich schnell, und mit ein paar Programmiertricks nähert sich die Komplexität ~ O(log(n)).

Um es klar zu sagen, meine Güte Die aktuelle Implementierung ist folgende:

longnum fact(const DWORD &x,longnum &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) = Multiplikation(i=2,3,5,7,11,13,17,...) von ( i ^ sum(j=1,2,3 ,4,5,...) von (4N/(i^j))-(2N/(i^j)) )

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?

Das obige ist der detaillierte Inhalt vonWie kann ich den Exponenten einer Primzahl „i' im T2-Term einer Fakultät effizient berechnen, wobei Exponent(i) = Summe(j=1,2,3,4,5,...) von (4N/( i^j)) - (2N/(i^j))?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!