n-th non-square

Problem:
Find the n-th non-square number.

(Adapted from Problem Solving Strategies, Arthur Engel)


If you have CS background, I invite you to come up with an O(log N) solution.

Done? Good. Below I present the O(1) approach.

Solution:
The n-th non-square number is given by $F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor$.

Proof:
Let G(n) be the same as F(n) except for the floor function.

Investigate $m \neq F(n)$. There is the largest $n$ s.t. $F(n) < m$. Hence $m+1 \leq F(n+1)$.
We conclude that $G(n) < m$ and $m+1 \leq G(n+1)$.

Rearranging the terms and squaring the inequalities, we get:
$n < (m-n-1/2)^2$ and $(m-n-1/2)^2 < n+1$, or
$n - 1/4 < (m-n)^2 - (m-n) < n + 3/4$.
Since the middle term is an integer, we see that $(m-n)^2 - (m-n) = n$. Simplifying, we get $m = (m-n)^2$, showing that m is a square.

In other words, F(n) skips all squares.

Now, we will show that F(n) is the n-th non-square number. The proof is by counting.
Fix k. We note that $F(k^2) = k^2 + k$. Hence There are $k^2$ terms of F(n) $\leq k^2 + k$.
On the other hand, we know that there are k squares $\leq k^2 + k$. Hence F(n) iterates through all the non-square numbers $\leq k^2 + k$. Therefore we conclude that F(n) is the n-th non-square.

QED