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))?

The problem in the question is to find a fast way to compute the T2 term in the expression for fast exact bigint factorial. The T2 term is defined as:

This is already pretty fast, and with some programming tricks the complexity nears ~ O(log(n)).

To be clear, my current implementation is this:

longnum fact(const DWORD &x)

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

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

T2 = T2 * N!

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

T2(4N) = multiplication(i=2,3,5,7,11,13,17,...) of ( i ^ sum(j=1,2,3,4,5,...) of (4N/(i^j))-(2N/(i^j)) )

The above is the detailed content of 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))?. For more information, please follow other related articles on the PHP Chinese website!