12
$\begingroup$

This question already has an answer here:

$$ \sum_{i=1}^N\left\lfloor\frac{N}{i}\right\rfloor $$ Is there a closed form expression to the above sum? (Mathematica doesn't give me anything)

$\endgroup$

marked as duplicate by YuiTo Cheng, Yanior Weg, Xander Henderson, José Carlos Santos, Ak19 Jun 13 at 0:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $N\ln(N)$ would be a good approximation. $\endgroup$ – Guy Apr 5 '14 at 6:40
  • $\begingroup$ It doesn't have an exact closed form. $\endgroup$ – Guy Apr 5 '14 at 6:41
  • $\begingroup$ Can you give me a reference? $\endgroup$ – Priyatham Apr 5 '14 at 6:41
  • $\begingroup$ @howardh. No, take N = 8, i = 3. $\lfloor \frac{8}{3}\rfloor = 2$ $\endgroup$ – Priyatham Apr 5 '14 at 7:03
  • $\begingroup$ @Priyatham Right, I don't know what I was thinking. $\endgroup$ – howardh Apr 5 '14 at 7:04
8
$\begingroup$

This is Dirichlet's divisor summatory function $D(x)$. It is known that $$D(x) = x\log x + x(2\gamma -1) + \Delta(x)$$ and the non-leading term $\Delta(x)$ is $O(\sqrt{x})$. Forget about its closed form, even the behaviour of the non-leading term $\Delta(x)$ is a well known unsolved problem.

Dirichlet divisor problem

Find the smallest value of $\theta$ for which $\Delta(x) = O(x^{\theta+\epsilon})$ holds true for all $\epsilon > 0$.

$\endgroup$
  • $\begingroup$ Thanks for the answer and the link. In the end I used the $O(\sqrt{x})$ formula for evaluating this sum. $\endgroup$ – Priyatham Apr 5 '14 at 7:44
6
$\begingroup$

$$\sum_{i=1}^N \left \lfloor \frac{N}{i}\right\rfloor \approx \sum_{i=1}^N \frac{N}{i} = N\sum_{i}^N \frac1{i} = NH_N$$

where $H_n$ is the nth Harmonic number.

For any monotonically decreasing function $f$ we have,

$$\int_1^{n+1}f(x)\,{\rm d}x \le \sum_{i=1}^n f(i) \le 1+\int_1^nf(x)\,{\rm d}x$$

Taking $f(x)=\frac1{x}$, we obtain the well known bound,

$$\ln(n+1)\le H_n\le 1+\ln(n)$$

Thus $H_n \sim \ln(n)$

and our sum is $$S=N\ln(N)$$

Note: $H_n=\ln(n) + \gamma$ is a better approximation, where $\gamma$ is the Euler Mascheroni Constant.


We can always say that

$$N\ln(N+1) \le S \le N + N\ln(N)$$

$\endgroup$
  • $\begingroup$ Yes I did. But like told @V.C., I need an exact answer. Also, when you say $n$, do you mean $N$? $\endgroup$ – Priyatham Apr 5 '14 at 7:01
  • $\begingroup$ @Priyatham yes I corrected the typo. But till date a closed form hasn't been found. $\endgroup$ – Guy Apr 5 '14 at 7:08
  • $\begingroup$ Also, since it's a discontinuous function on integers, you can be almost sure that an analytic closed form doesn't exist. $\endgroup$ – Guy Apr 5 '14 at 7:09
  • 1
    $\begingroup$ @Priyatham. There is no hope to arrive to any closed form solution (as already other wrote). The only thing you can hope is to find upper and lower bounds and what Sabyasachi answered is probably almost the best you could get. $\endgroup$ – Claude Leibovici Apr 5 '14 at 7:25
  • $\begingroup$ Why is the possibility of a closed form so pessimistically viewed? As far as I understand, Sabyasachi's approximation is already asymptotic to the true value of the function. Now, why does the discontinuity by it self make it "almost sure" that a better, perhaps, exact analytical closed form does not exist - like the gamma function for the factorials? $\endgroup$ – Just_a_fool Apr 5 '14 at 9:58
1
$\begingroup$

The sequence $a_n=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor$ is integer sequence A006218 in the OEIS. It is equal to a function called the divisor summatory function; i.e., it is equal to the sum over the divisor function:

$$a_n=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor=\sum_{k=1}^{n}d(k)=D(n).$$

$\endgroup$

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