Sum of floor functions

Question

For a positive integer $n$, let $$\def\fl#1{\left\lfloor\frac n{#1}\right\rfloor}f(n)=\fl 1+\fl2+\fl3+\cdots+\fl n.$$ Find $f(1,000,000)−f(999,999)$. I know the changes in the floors will take place when the denominator is a factor of the numerator. But it is a long process. Is a simpler process available.

Answer 1

Consider what happens to a specific summand in the one case compared to the other:

$\lfloor \frac{n}{k}\rfloor$ compared to $\lfloor \frac{n-1}{k}\rfloor$

One of two things will be true. Either $n\equiv 0\mod k$ or you will have that $n\equiv r\mod k$ with $1\leq r<k$

If $n\equiv r\mod k$ (i.e. there is a positive remainder), then it follows that $\lfloor \frac{n}{k}\rfloor = \lfloor \frac{n-1}{k}\rfloor$

Else, with $n\equiv 0\mod k$ you have $\lfloor\frac{n}{k}\rfloor = \lfloor\frac{n-1}{k}\rfloor + 1$

Since $n\equiv 0\mod k$ implies that $k$ is a factor of $n$, it should quickly follow that $f(n)-f(n-1) = d(n)$ where $d(n)$ counts the number of factors of $n$.

The number of factors of 1,000,000 can be found via multiplication principle. $1,000,000=10^6 = 2^65^6$. Each different factor will be of the form $2^a5^b$, there are 7 choices for $a$ and 7 choices for $b$, hence there are 49 factors.

$f(1,000,000)-f(999,999) = 49$