MathGroup Archive 2013

[Date Index] [Thread Index] [Author Index]

Search the Archive

Can I use Mathematica to simplify this recursive function definition

Here's my recursive function with its terminating conditions:

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

And what I'm interested in is explicit / non-recursive expressions for d[n,2,2], d[n,3,2], d[n,4,2], d[n,5,2], d[n,6,2], and so on for positive integer values of k > 1, with "a" always 2.  Is there a way to make Mathematica give me that?

If I type "d[n,2,2]" or "d[n,3,2]" into Mathematica, I immediately get a stack overflow, so that's no help.

If I manually work through the recursion for d[n,2,2] by hand and do a fair bit of simplifying, I am eventually left with

 1 - Floor[ n^(1/2)]^2 + 2 Sum [ Floor[ n/m], {m, 2, Floor[n^(1/2)]}]

And if I manually work through d[n,3,2] by hand (and do a huge amount of simplifying - it's a pain to do), I arrive at

-1 + Floor[ n^(1/3)]^3 +
 3 Sum[ Floor[ n/(m^2)] - Floor[ Floor[n/m]^(1/2)]^2 +
    2 Sum[ Floor[Floor[n/m]/j], {j, m + 1,
       Floor[Floor[n/m]^(1/2)]}], {m, 2, Floor[n^(1/3)]}]

So that's the sort of output I'm looking for.  I'd like to be able to get expressions like that for integers k between 2 and, say, 10 (the number of terms is 2^k, so there are limits here).

If it's any help, d is a recursive definition of one generalization of the Dirichlet hyperbola method - in fact, d[n,2,1] computes D(x), the sum at the heart of the Dirichlet Divisor problem.  But I'm interested in counting divisors that exclude 1, hence "a" set to 2 in the function definition.


  • Prev by Date: Re: problems with FrameTicks
  • Next by Date: Re: Using manipulate with user entered variables and functions
  • Previous by thread: Re: problems with NDSolve
  • Next by thread: Re: Using manipulate with user entered variables and functions