0
$\begingroup$

How can I speed up the execution of following function, specifically for larger values of n?

f[n_, 0, s_, a_] := 1
fr[n_, s_] := fr[n, s] = Sum[N[m^-s], {m, 1, n}]
f[n_, 1, s_, a_] := f[n, 1, s, a] = fr[Floor[n], s] - fr[a, s]
f[n_, k_, s_, a_] := 
 f[n, k, s, a] = 
  N[Sum[Binomial[k, j] (m^-s)^j f[Floor[n/(m^j)], k - j, s, m], {j,
  1, k}, {m, a + 1, Floor[n^(1/k)]}]]

For reference, n, k, and a should all be positive integers. s should be any complex number.

$\endgroup$
0
3
$\begingroup$

This seems to be somewhat faster. I use N[] or equivalent thereof in some places. Also removed a Floor since the argument had to be integral anyway.

Clear[f, fr]
f[n_, 0, s_, a_] := 1
fr[n_, s_] := fr[n, s] = Sum[m^-s, {m, 1., n}]
f[n_, 1, s_, a_] := f[n, 1, s, a] = fr[n, s] - fr[a, s]
f[n_, k_, s_, a_] := 
 f[n, k, s, a] = 
  N[Sum[Binomial[k, j] (N[m]^-s)^j f[Floor[n/(N[m]^j)], k - j, s, 
      m], {j, 1, k}, {m, a + 1., Floor[N[n]^(1./k)]}]]

There may be further improvements to be had but this could at least be a start.

$\endgroup$
7
  • 1
    $\begingroup$ Isn't HarmonicNumber[n, s]//N faster than Sum[m^-s, {m, 1., n}]? $\endgroup$ – Dr. belisarius Dec 19 '14 at 17:45
  • 1
    $\begingroup$ With its current hat your avatar remembers me a few Star Trek episodes :) $\endgroup$ – Dr. belisarius Dec 19 '14 at 17:47
  • 2
    $\begingroup$ @DanielLichtblau I can just about picture you as the scientific officer from Vulfram. $\endgroup$ – Yves Klett Dec 19 '14 at 18:26
  • 1
    $\begingroup$ @Yves Klett When I was younger I kept long hair to hide my pointy ears (they receded with age). $\endgroup$ – Daniel Lichtblau Dec 19 '14 at 19:39
  • 1
    $\begingroup$ @Yves Klett That's "Dr. Legolas", to you. $\endgroup$ – Daniel Lichtblau Dec 19 '14 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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