MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following well known identity, where $\tau(n)$ denotes the number of divisors of $n$ appears in many number theory texts $$ \sum_{k=1}^n \tau(k) = \sum_{d=1}^n \lfloor n/d \rfloor, $$ and follows from the observation that "one out of d" integers in $\{1,2,\ldots,n\}$ are multiples of $d$ and then summing along rows $d$ as well as along columns $k$ the indicator function $1\{~ d~\mathrm{divides}~k~\}$.

Is there a good approximation, or are there any identities related to the following sum, preferably containing arithmetic functions? $$ \sum_{d=1}^n \lfloor n/d \rfloor^2 $$

share|cite|improve this question
The sequence isn't in OEIS if I computed it correctly. – joro Apr 22 '12 at 9:51

Sums of this sort are well known to the experts - but since none of them have answered so far, let me try. Denoting the fractional part of a real $x$ by $\{x\}$, you can write your sum as $$ S = n^2 \sum_{d=1}^n \frac1{d^2} - 2n \sum_{d=1}^n \frac1d\left\{\frac nd\right\} + \sum_{d=1}^n \left\{\frac nd\right\}^2 = \frac{\pi^2}{6}\, n^2 + O(n\log n). $$

If you need more precision, you have to find the main term of the sum $\sum_d d^{-1}\{d^{-1}n\}$. The standard technique here, I believe, would be to use the Fourier expansion of the fractional part function, but you'd better contact experts for details, to avoid re-inventing the wheel.

Here is a different kind of answer, depending on what you are after. Your sum counts the number of triples $d,x,y\in[1,n]$ with $xd,yd\le n$. Since there are $\sum_{k=1}^n \tau(k)$ such triples with $x=y$, splitting the sum into two part according to whether $x\ge y$ or $y\ge x$, we can write it as $$ S = 2 \sum_{dx\le n} x - \sum_{k=1}^n \tau(k). $$
Letting $k=dx$, we get $$ S = 2 \sum_{k=1}^n \sigma(k) - \sum_{k=1}^n \tau(k), $$ where $\sigma$ is the sum-of-divisors function. This gives you ``an identity containing arithmetic functions'', as you requested.

share|cite|improve this answer
@Seva: Thank you that's very helpful, and I will look into the fourier expansion of the fractional part function – kodlu Apr 22 '12 at 21:20
See my response for a supplement. – GH from MO Apr 23 '12 at 0:58

This is a supplement to Seva's answer. The error term $O(n\log n)$ can be improved, but not considerably. $S$ is the summatory function of $2\sigma(k)-\tau(k)$ which exceeds $k\log\log k$ infinitely often, hence there is no continuous approximation to $S$ with an error less than $n\log\log n$. For $\sum_{k=1}^n\tau(k)$ the error can be improved to $(2\gamma-1)n+O(n^{7/22})$ or even better, but for $\sum_{k=1}^n\sigma(k)$ the best known error is $O(n(\log n)^{2/3})$, due to Walfisz (1963). See Chapter I.3 in Tenenbaum's Introduction to analytic and probabilistic number theory.

share|cite|improve this answer
@GH: Thanks. How would the answers change if the upper limit of the sum was $v=v(n)$ for some positive, monotone function of $n$ satisfying $1< v(n) < n$? And what if the moment wasn't second but a higher moment? Perhaps $k=3,4$ and the sum was generalized to $$ \sum_{d=1}^{v} \lfloor n/d \rfloor^k $$ And where can I find information, if any, on the fourier expansion of the fractional part function? – kodlu Apr 23 '12 at 1:47
@kodlu: Smaller terms do not necessarily yield a better error term. For example, the error term in the summatory function of the Mobius function is extremely tricky, closely connected to the Riemann Hypothesis. Regarding your second question: each moment is a different story. You see, my response only supplements Seva's which describes your sum in more arithmetic terms. The Fourier expansion of the fractional function is classical, see e.g.… Of course the coefficients don't decay fast as the function is not continuous. – GH from MO Apr 23 '12 at 4:05

On your comment concerning the sum $\sum_{d\leq n}\lfloor{n/d}\rfloor^k$ for various values of $k$

$$\sum_{n\leq x}[\frac{x}{n}]^k=\sum_{n\leq x}\sum_{m\leq \frac{x}{n}}m^{k}-(m-1)^k=\sum_{n\leq x}\sum_{d\mid n}d^k-(d-1)^k$$

And since, $$\sum_{d\mid n} d^k-(d-1)^k=\sum_{d\mid n}(d^k-\sum_{j=0}^k\binom{k}{j}d^{k-j}(-1)^j)=\sum_{d\mid n}\sum_{j=1}^k \binom{k}{j}d^{k-j}(-1)^{j-1}$$

We get that, $$\sum_{n\leq x}[\frac{x}{n}]^k=\sum_{j=1}^k\binom{k}{j}(-1)^{j-1}\sum_{n\leq x}\sigma_{k-j}(n)$$ For all $k\ge 1$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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