Here is my solution so far, but it just doesn't seem right:

Define a function $\sigma_0(x) = \sum\limits_{d \mid x} 1$ on the interval $[1, N]$. The partitions for the Riemann Sum will be of equal length 1 from $[1, N]$. Further, let $x_j = j$ for $j = 1, 2, \ldots, N$. Define $$R_N = \sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} \left( \frac{N}{j} - \left\lfloor\frac{N}{j}\right\rfloor\right)$$ Now, we can use Riemann Sums to estimate that $$\sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} 1\approx \int_{1}^{N} \left[\sum\limits_{d \mid x} 1\right]dx = \sum\limits_{j = 1}^{N} \left\lfloor \frac{N}{j} \right\rfloor$$ Further, since $R_N$ is always greater than 0 but strictly less than $N$, we have that $$A(N) = \frac{1}{N} \sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} 1 \approx \frac{1}{N} \sum\limits_{j = 1}^{N} \left\lfloor \frac{N}{j} \right\rfloor \approx \frac{1}{N} \log(N) + C$$ Recall that the error between the actual value of an integral and its approximation by a finite sum of rectangles is bounded by the width of the rectangles multiplied by the maximum value of the integrand. In our case, $\left\lfloor\frac{N}{j}\right\rfloor$ is the maximum value of the integrand and $\frac{1}{N}$ is the width of each rectangle. Thus, the error is at most $$\frac{1}{N} \left\lfloor\frac{N}{j}\right\rfloor$$ which is equal to 1 when $j = 1$. Therefore the error is bounded by 1.

I am quite lost, so if someone could please help correct my mistakes.


1 Answer 1


Just observe that: $\left\lfloor \frac{n}{j} \right\rfloor$$\leq \frac{n}{j}$. So, $$\frac{1}{n} \sum_{j=1}^{n} \left\lfloor \frac{n}{j} \right\rfloor < \frac{1}{n} \sum_{j=1}^{n} \frac{n}{j} = \sum_{j=1}^{n} \frac{1}{j} < \log(n) +1.$$ You can find the approximation of the harmonic sum here.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .