6
$\begingroup$

I compute the following:

schA[n_?EvenQ] := 
 N[Sum[Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 0, (n/2) - 1}]]

schB[n_?EvenQ] := N[schA[n]/(n/2)]

sch[n_?EvenQ] := schB[n] + N[Log2[(n/2)]]

I ran the function sch[n] for n = 5000 which takes considerable time to complete. Is there a way to speed this up? I'd like to check up to one million or higher.

$\endgroup$
0

3 Answers 3

8
$\begingroup$

The relatively new command AsymptoticSum does the job.

AsymptoticSum[Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 0, (n/2) - 1}, 
n -> Infinity] // Simplify;

Log[E^((-1 + n - 9 n^3 + 6 n^3 Log[n] + 2 n^2 (Log[64] + 3 Log[\[Pi]]))/(12 n))/(Glaisher n^(1/12))]/Log[2]

schA[n_?EvenQ] := N[Log[E^((-1 + n - 9 n^3 + 6 n^3 Log[n] + 
2 n^2 (Log[64] + 3 Log[\[Pi]]))/(12 n))/(Glaisher n^(1/12))]/Log[2]]
schA[10^7]

1.05447*10^15

and so on.

PS. The result of the command

NMaximize[{RealAbs[
 Log[E^((-1 + n - 9 n^3 + 6 n^3 Log[n] + 
          2 n^2 (Log[64] + 3 Log[\[Pi]]))/(12 n))/(Glaisher n^(1/
          12))]/Log[2] - 
  Sum[Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 
    0, (n/2) - 1}]]/
Sum[Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 0, (n/2) - 1}]*
   Sqrt[n], n >= 10^6}, n]

{4.75504*10^-13, {n -> 1.00001*10^6}}

gives an estimate of the accuracy for big n.

$\endgroup$
6
  • $\begingroup$ Am I correct in assuming that this produces an approximation of the sum, which works for large values of n? I am carrying out experiments in relation to a lower-bound so need exact values. Is there info on the accuracy of AsymptoticSum? $\endgroup$ Oct 20, 2022 at 11:12
  • 1
    $\begingroup$ Your assumption is correct. I dont know any info about the accuracy of AsymptoticSum. As I understand it, AsymptoticSum uses Series[Sum[ Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 0, (n/2) - 1}], {n, Infinity, 2}] here, which results in $\endgroup$
    – user64494
    Oct 20, 2022 at 12:15
  • $\begingroup$ $$ \frac{\log \left(\left(\sqrt{2 \pi } \sqrt{\frac{1}{n}}+\frac{1}{6} \sqrt{\frac{\pi }{2}} \left(\frac{1}{n}\right)^{3/2}+O\left(\left(\frac{1}{n}\right)^{5/2}\right)\right) \exp \left(\frac{1}{4} (2 \log (n)-3) n^2+\frac{1}{2} (\log (2)+\log (2 \pi )) n+\frac{1}{12} (-12 \log (A)+5 \log (n)-6 \log (2 \pi )+1)-\frac{1}{12 n}-\frac{1}{240 n^2}+O\left(\left(\frac{1}{n}\right)^3\right)\right)\right)}{\log (2)}.$$ $\endgroup$
    – user64494
    Oct 20, 2022 at 12:17
  • $\begingroup$ What is A in the above formula ? Is it Glaisher's constant ? $\endgroup$ Oct 20, 2022 at 14:17
  • $\begingroup$ @underranrand: I think yes, $A$ stands for Glaisher's constant. $\endgroup$
    – user64494
    Oct 20, 2022 at 15:00
8
$\begingroup$

One can numericize inside the summation to avoid intermediate swell, and also use LogGamma to avoid computing large factorial products and then taking logarithms thereof.

schAx[n_?EvenQ] := (n/2) + 
  1/Log[2]*(Sum[LogGamma[i + 1.] + LogGamma[n - i], {i, 0, (n/2) - 1}])
schBx[n_?EvenQ] := schAx[n]/(n/2.)
schx[n_?EvenQ] := schBx[n] + Log2[(n/2.)]

Compare:

In[67]:= sch[10000] // Timing
schx[10000] // Timing

Out[67]= {1.53963, 111253.}

(* Out[68]= {0.001467, 111253.} *)

In[70]:= schx[10^6] // Timing

(* Out[70]= {0.136898, 1.77675*10^7} *)
$\endgroup$
2
  • $\begingroup$ The LogGamma was a nice idea. Now after changing index variables in the second sum from n-i to something like r then change again to i, the sum becomes Sum[LogGamma[i],{i,1,n}] which according to Mathematica is equal to LogBarnesG[1 + n] and so no explicit Sum and maybe Mathematica has cool tricks to compute that function. $\endgroup$ Oct 20, 2022 at 13:59
  • $\begingroup$ Sum[Log2[2*Factorial[i]*Factorial[n - 1 - i]], {i, 0, (n/2) - 1}] results in Log[2^(n/2) BarnesG[n] Gamma[n]]/Log[2]. $\endgroup$
    – user64494
    Oct 20, 2022 at 15:17
6
$\begingroup$

Since $\prod_{k=0}^{n-1} k! = \prod_{k=1}^{n-1} k^{n-k}$, another possibility is

schAy[n_?EvenQ] := N[Range[1,n-1]] // Reverse[#].Log2[#] + N[Log2[2]]*n/2&

Comparison with OPs function:

schA[10000]//AbsoluteTiming
(* {2.05008,5.56202*10^8} *)

schAy[10000]//AbsoluteTiming
(* {0.000843,5.56202*10^8} *)

Example with larger $n$:

schAy[10^7]//AbsoluteTiming
(* {0.281514,1.05447*10^15} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.