# Problem with my floor…

Let the set of numbers $A,n$ be of defined as $A_n = \text{the }n\text{'th value of }x\text{ such that }2\not\mid\lfloor{ x^2 - \sqrt{x}}\rfloor$, and $n$ is a positive integer.

So as the first 10 sums are: \begin{align} x&&\lfloor{ x^2 - \sqrt{x}}\rfloor\\ 1 &&0\\ 2 &&2\\ 3 &&7\\ 4 &&14\\ 5 &&22\\ 6 &&33\\ 7 &&46\\ 8 &&61\\ 9 &&78\\ 10 &&96\\ \end{align}

The terms of $A$ is $A_1 = 3, A_2 =6,A_3 = 8,$ and so on.

I'm trying to determine whether the following is correct:

$$2 n+\lfloor{\frac{1}{2}+\frac{1}{2} \sqrt{8 n - 7}}\rfloor = A_n$$

This is a real pain, as I have little to no experience in working with the floor function. How can this be (dis)proven?

Any help would be appreciated.

-
I think you want to reverse / simplify the definition to the nth positive $x$ for which the floor of $x^2=\sqrt{x}$ is odd. –  coffeemath Dec 27 '13 at 0:02
The notation $a|b$ means that $a$ divides $b$, so you should say $2\not |...$. –  Ragnar Dec 27 '13 at 0:10

You want $\lfloor{ x^2 - \sqrt{x}}\rfloor$ to be odd. Because you only look at integers $x$, we know that $\lfloor{ x^2 - \sqrt{x}}\rfloor=x^2+\lfloor -\sqrt x\rfloor=x^2-\lceil\sqrt x\rceil$. Now, you want $\lceil \sqrt x\rceil$ to have the opposite parity of $x$ (because $x^2$ has the same parity as $x$. You know that $\lceil\sqrt x\rceil$ is odd when $(2k)^2<x\leq(2k+1)^2$ for some integer $k$. It is even when $(2k+1)^2< x\leq(2k+2)^2$.
Now, we find the following values: $$3,6,8,11,13,15,18,20,22,24,27,29,31,33,35,38,\dots$$ As you can see, you get all even or odd values between consecutive squares, and when crossing a square, you change the parity. Also, the differences are always $2$, except when crossing a square; then they are $3$.
We know every group of numbers of the same parity is one larger than its predecessor. We want to solve $\frac{k(k+1)}2=n$ to find the number of the group $n$ is in. This is what we want to add to $2n$ to make a correction for the steps of size $3$. Solving it gives $\lfloor\frac{1}{2} \left(\sqrt{8 n+1}-1\right)\rfloor$. We still have to add $1$ to correct for the offset. (this can/should be proven/explained more carefully) Now, we obtain exactly the formula you gave yourself. This is (almost) enough explanation to make it a proof IMO.