Double Sum Involving Condition
A story of incremental improvement
Let's look at the OP's original expression again, for reference:
$$\sum_{m=1}^{c}\frac{1}{m}\sum_{d \mid m}\mu(d)n^{m/d}$$
Most people here are familiar with Sum[]
, and would not have much trouble translating the outer summation into Mathematica syntax. The inner part,
$$\sum_{d \mid m}\mu(d)n^{m/d}$$
is not terribly familiar to those who do not do much number theory. What this basically is saying is that the terms of the sum are indexed over the divisors of $m$. Appropriately enough, Mathematica does have a Divisors[]
function. The inner sum can thus be written as
Sum[MoebiusMu[d] n^(m/d), {d, Divisors[m]}]
Summing over the divisors of a number, however, is so common a number-theoretic operation that Mathematica has seen it fit to provide a DivisorSum[]
function. Thus, the inner sum can also be written as
DivisorSum[m, MoebiusMu[#] n^(m/#) &]
The story does not end here. The operation
$$\sum_{d \mid m}f(d)g(m/d)$$
frequently turns up in number-theoretic and other contexts, that it has been given a special name: Dirichlet convolution. Mathematica, fortunately, also provides a function for evaluating convolutions, called DirichletConvolve[]
. Thus, the inner sum is most compactly expressed as
DirichletConvolve[MoebiusMu[j], n^j, j, m]
The function in the OP can now be implemented like so:
diml[c_Integer?Positive, n_Integer?Positive] := Block[{j},
Sum[DirichletConvolve[MoebiusMu[j], n^j, j, m]/m, {m, c}]]
or, using formal symbols as suggested by The Doctor,
diml[c_Integer?Positive, n_Integer?Positive] :=
Sum[DirichletConvolve[MoebiusMu[\[FormalJ]], n^\[FormalJ], \[FormalJ], m]/m, {m, c}]
(They look messy here on SE, but should look nice when pasted into Mathematica.)
Here is the function in action:
Table[diml[c, n], {c, 5}, {n, 5}]
{{1, 2, 3, 4, 5}, {1, 3, 6, 10, 15}, {1, 5, 14, 30, 55},
{1, 8, 32, 90, 205}, {1, 14, 80, 294, 829}}
Please see J.M.'s answer (in comments) using DirichletConvolve
. I would vote for this as an answer.
I present my answer:
l[c_, n_] :=Module[{r = Range[c]},
Total[(1/r) Total /@MapThread[MoebiusMu@#1 n^(#2/#1) & ,{Divisors /@ r, r}]]]
I will happily delete and vote for JM answer.
I like J.M.'s answer and voted for it. However, it's hard to format comments, so I've posted this as an answer instead. Rather than using Block[{j},...]
, you can use formal symbols instead, used to represent a formal parameter that will never be assigned a value. Moreover, if you enter
DivisorSum[m, Function[d, MoebiusMu[d] n^(m/d)]] // TraditionalForm
you will see that Mathematica uses formal symbols automatically. Also, in many cases, I prefer to use the "map notation" for Function
instead of #
and &
. For example,
is executable code for this function.
Finally, in TraditionalForm
notation, the sum can be expressed as
which corresponds nicely to the original sum posted in the question. However, using DirichletConvolve
should be more efficient.