3 of 7 Try retyping first $2$ equations and add explanation that it may not show properly.

I'm adding a new answer instead of updating or adding to my original one since this is quite different based on the new information provided. The answers by Ethan Bolker and Fabio Somenzi involve using (note: the following $$2$$ equations may not display properly, although they appear to be written correctly & show fine in Edit mode)

$$a + 2n(b - n) = k(b - 2n) \tag{1}\label{eq1}$$

to create a quadratic equation in $$n$$, i.e.,

$$n^2 - (k + b)n + \frac{bk - a}{2} = 0 \tag{2}\label{eq2}$$

which has a discriminant of

$$D = (bk - a)^2 - 2(bk - a) = k^2 + b^2 + 2a \tag{3}\label{eq3}$$

The value of $$n$$ is

$$n = \frac{k + b \pm \sqrt{D}}{2} \tag{4}\label{eq4}$$

The smallest positive integer $$n$$ comes from subtracting $$\sqrt{D}$$ where $$D$$ is a perfect square of the same parity as $$k + b$$, and less than but as close as possible to $$(k + b)^2$$. Thus, from \eqref{eq3}, you want to start with the smallest $$k$$ such that $$bk - a \gt 0$$, say $$k_0$$, so

$$b \ge bk_0 - a > 0 \; \Rightarrow \; -2b \le -2(bk_0 - a) \lt 0 \tag{5}\label{eq5}$$

From \eqref{eq3},

$$(k_0 + b)^2 - 2(bk_0 - a) \ge k_0^2 + 2bk_0 + b^2 - 2b \tag{6}\label{eq6}$$

However, note that

$$(k_0 + (b - 1))^2 = k_0^2 + 2bk_0 + b^2 - 2b + (1 - 2k_0) \tag{7}\label{eq7}$$

Thus, the next smaller perfect square of $$D$$ is $$(k_0 + (b - 1))^2$$. Note going from $$m^2$$ to $$(m + 1)^2$$ involves adding $$2m + 1$$, then to $$(m + 2)^2$$ involves adding $$2m + 3$$, then add $$2m + 5$$ to get $$(m + 3)^2$$, etc. In other words, even for very large integers, you can quickly and easily go from a perfect square to the next perfect square by adding a value which you increment by $$2$$ each time. Thus, starting at $$k = k_0$$ in \eqref{eq3}, and using \eqref{eq7}, you can quickly determine each next value for $$k$$ and compare it to the next possible perfect square, incrementing each value(s) as appropriate, until the values match, and the result gives an integer in \eqref{eq4}. This is relatively efficient, and is generally considerably faster than doing integer divisions (e.g., for factoring or to check modulo values). For example, https://agner.org/optimize/optimizing_cpp.pdf says at section 14.5 Integer division:

Integer division takes much longer time than addition, subtraction and multiplication (27 - 80 clock cycles for 32-bit integers, depending on the processor).

This speed issue will vary with things like the size of the integers, the compiler being used, etc., but I believe in basically all cases that integer division will be quite slow.

 answered May 12 at 8:39 John Omielan 14.9k22 gold badges88 silver badges3131 bronze badges