Home > Algebra, Problem Solving > n-th number which is not a square

## n-th number which is not a square

Find a closed form (i.e. an explicit formula in terms of $n$) for the $n$-th number which is not a perfect square.

Solution
If we denote $a_n$ as being the $n$-th number which is not a square, we can see that the following recurence holds:
$a_{n+1}=\begin{cases} a_n+1, & n\neq k(k+1), k \in \mathbb{N} \\ a_n+2, & n=k(k+1),\ k \in \mathbb{N} \end{cases}$
Further more, we conjecture that $a_{k(k+1)}=(k+1)^2-1$ and $a_{k(k+1)+1}=(k+1)^2+1$. We see that for $k=1$ we have $a_2=3$ and $a_3=5$. We begin now to prove our conjecture by induction. Assume that $a_{k(k+1)+1}=(k+1)^2+1$. Then, using our recurence discovered earlier, we can see that $a_{(k+1)(k+2)-1}=a_{k^2+3k+1}=a_{k(k+1)+2k+1}=a_{k(k+1)}+2k+1=k^2+4k+3=(k+2)^2-1$, and hence $a_{(k+1)(k+2)+1}=(k+2)^2+1$. By mathematical induction we can say now that the conjecture is true always. Now, if given $n \in \mathbb{N}$ we can find $k \in \mathbb{N}$ in terms of $n$ such that $k(k+1), then we are almost done.

We have the following equivalences:
$k(k+1) < n \leq (k+1)(k+2) \iff$
$k^2+k < n \leq k^2+3k+2 \iff$
$4k^2+4k+1 < 4n+1 \leq 4k^2+12k+9 \iff$
$2k+1 < \sqrt{4n+1} \leq 2k+3 \iff$
$-k-1 \leq -\frac{\sqrt{4n+1}-1}{2} < -k \iff$
Therefore $k=-1-\left[\frac{1-\sqrt{4n+1}}{2} \right]$, where $[a]$ is the greatest integer not exceeding $a$.
To find $a_n$ we proceed as follows:
$a_n=a_{k(k+1)+1+n-k(k+1)-1}=a_{k(k+1)+1}+n-1-k(k+1)$. Replacing $k$ we get a very crowded formula which is correct.

$a_n=(\left[ \frac{1-\sqrt{4n+1}}{2} \right])^2+n-(-\left[ \frac{1-\sqrt{4n+1}}{2} \right])(-1-\left[ \frac{1-\sqrt{4n+1}}{2} \right])$. Simplyfying, we get
$a_n=n-\left[ \frac{1-\sqrt{4n+1}}{2} \right].$

Another closed form
$\displaystyle n+ \left\lfloor \sqrt{n}+\frac{1}{2}\right\rfloor$.