How to speed up execution of this function?

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.

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.

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