4

Consider '\' to be the integer division operator, i.e.,

$a$ \ $b = \lfloor a / b\rfloor$

Is there a formula to compute the following summation:

N\1 + N\2 + N\3 + ... + N\N

AncientEgypt
  • 45

1 Answers1

3

This is not a closed form, but an alternate characterization of this sum is $$ \sum_{k=1}^n\lfloor n/k\rfloor=\sum_{k=1}^nd(k)\tag{1} $$ where $d(k)$ is the number of divisors of $k$. This can be seen by noticing that $\lfloor n/k\rfloor$ increases by $1$ when $k\mid n$:

$$ \begin{array}{c|cc} \lfloor n/k\rfloor&1&2&3&4&5&6&k\\ \hline\\ 0&0&0&0&0&0&0\\ 1&\color{#C00000}{1}&0&0&0&0&0\\ 2&\color{#C00000}{2}&\color{#C00000}{1}&0&0&0&0\\ 3&\color{#C00000}{3}&1&\color{#C00000}{1}&0&0&0\\ 4&\color{#C00000}{4}&\color{#C00000}{2}&1&\color{#C00000}{1}&0&0\\ 5&\color{#C00000}{5}&2&1&1&\color{#C00000}{1}&0\\ 6&\color{#C00000}{6}&\color{#C00000}{3}&\color{#C00000}{2}&1&1&\color{#C00000}{1}\\ n \end{array} $$ In the table above, each red entry indicates that $k\mid n$, and each red entry is $1$ greater than the entry above it. Thus, the sum of each row increases by $1$ for each divisor of $n$.

A simple upper bound is given by $$ n(\log(n)+\gamma)+\frac12\tag{2} $$ This is because we have the following bound for the $n^\text{th}$ Harmonic Number: $$ H_n\le\log(n)+\gamma+\frac1{2n}\tag{3} $$ where $\gamma$ is the Euler-Mascheroni Constant.

Research Results

After looking into this a bit, I found that the Dirichlet Divisor Problem involves estimating the exponent $\theta$ in the approximation $$ \sum_{k=1}^nd(k)=n\log(n)+(2\gamma-1)n+O\left(n^\theta\right) $$ Dirichlet showed that $\theta\le\frac12$ and Hardy showed that $\theta\ge\frac14$.

There is no closed form known for $(1)$.

robjohn
  • 345,667