# On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$ [duplicate]

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)

-

## marked as duplicate by Claude Leibovici, Davide Giraudo, Hakim, amWhyNov 6 '14 at 12:23

It looks like it is integer by definition... –  Bach Mar 15 '14 at 14:06
@Bach: Yes , it is an integer ... –  Souvik Dey Mar 15 '14 at 14:10
Sorry, I missed the even in your question. –  Bach Mar 15 '14 at 14:13
This is INMO 2014 Question 2: olympiads.hbcse.tifr.res.in/subjects/mathematics/… –  barto Apr 5 at 21:12

$\left[\frac{n}{j}\right]$ is the number of positive integers $k$ such that $k\cdot j \leqslant n$. Thus
$$\sum_{j=1}^n \left[\frac{n}{j}\right] = \sum_{j\cdot k \leqslant n} 1 = \sum_{m = 1}^n \left(\sum_{j\cdot k = m} 1\right) = \sum_{m=1}^n \tau(m),$$
where $\tau(m)$ is the number of divisors of $m$. Every positive integer that is not a perfect square has an even number of divisors, while a perfect square has an odd number of divisors. There are $\left[\sqrt{n}\right]$ perfect squares $\leqslant n$. Hence
$$\sum_{j=1}^n \left[\frac{n}{j}\right] \equiv \left[\sqrt{n}\right] \pmod{2}.$$