The nonsquares

I want to create a function that returns the \(n\)-th nonsquare number. The nonsquare numbers are by definition the numbers sitting between the square numbers. The space between successive square numbers is one less than their distance:

$$\begin{array}{c|cccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & \ldots \\ \hline x^2 & 0 & 1 & 4 & 9 & 16 & 25 & \ldots \\ (x + 1)^2 - x^2 - 1 & 0 & 2 & 4 & 6 & 8 & 10 & \ldots \end{array}$$

It appears the gap size between the \(n\)-th square number and the \((n + 1)\)-th square number is \(2n,\) but we must prove it algebraically:

$$(x + 1)^2 - x^2 - 1 = x^2 + 2x + 1 - x^2 - 1 = 2x$$

Let's have a quick look at the nonsquares:

$$\begin{array}{c|cccccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \ldots \\ \hline y & 2 & 3 & 5 & 6 & 7 & 8 & 10 & 11 & 12 & 13 & \ldots \\[1em] x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \ldots \\ \hline y & 14 & 15 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & \ldots \end{array}$$

We can make the pattern more clear by subtracting \((x + 2)\) from our function:

$$\begin{array}{c|cccccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \ldots \\ \hline y - (x + 2) & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & \ldots \\[1em] x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \ldots \\ \hline y - (x + 2) & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & \ldots \end{array}$$

The value \(2\) in \(y - (x + 2)\) was chosen because \(2\) is the first nonsquare number. We know the gap between square numbers is an even number, but when listing the nonsquares, we're interested in positive gap sizes only. That's why in the following algorithm, the gap size \(i\) starts at \(2\) and increments by \(2\) on each step. Also note that \(y\) in the tables above corresponds to \(j\) in our program. That's why \(j\) starts at \(x + 2.\)


def nonsq(x):
	i = 2
	j = x + 2
	while x >= i:
		x -= i
		i += 2
		j += 1
	return j