When does $\lfloor\sqrt{x^2 + n}\rfloor = \lfloor\sqrt{(x-1)^2 + n}\rfloor$?

Question

Call $x \in[\sqrt{n},n/2] \cap \Bbb{Z} $ a critical point if the following holds

$$\left \lfloor\sqrt{x^2 + n}\right\rfloor = \left \lfloor\sqrt{(x-1)^2 + n} \right \rfloor$$

It appears that mostly this does not happen. For most of the time you have:

$$\left\lfloor\sqrt{x^2 + n}\right\rfloor = 1 + \left\lfloor\sqrt{(x-1)^2 + n}\right\rfloor$$

I can write some simple code to run through every $x$ from $\lceil\sqrt{n}\rceil$ to $n/2$ and just check to see when the equality holds but that is an $O(n)$ calculation and I'm sure there must be a faster way to do this.

I tried to massage the equation and remove the floor functions by being careful and such, but I keep winding up with trivial identities instead of things that will actually help me calculate the critical points.

Would really appreciate some help.

Answer 1

I would suggest that the values you want to consider are $$x=\bigg\lfloor \frac {n}{2k} - \frac{k}{2} +1 \bigg\rfloor$$ for positive integers $k$, in which case $\lfloor \sqrt{x^2+n}\rfloor =\lfloor \sqrt{(x-1)^2+n}\rfloor = x + k-1$,

although

• for odd $n$ this is greater than $\frac{n}{2}$ when $k=1$
• given $n$, this is less than $\sqrt{n}$ for large $k$: for example when $n=50$ and $k \ge 3$, though curiously when $n=49$ or $51$ only for $k \ge 4$