# 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, amWhy algebra-precalculus StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Nov 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 '15 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}.$$