<s>[INST] How to find the smallest positive integer $K$ such that $(K -\lfloor\frac{K}{2}\rfloor + 1)(\lfloor\frac{K}{2}\rfloor + 1) \geq N$ I am writing a program and I would need an explicit formula for the following:
The smallest positive integer $K$ such that:
$$\left(K - \left\lfloor\frac{K}{2}\right\rfloor + 1\right)\left(\left\lfloor\frac{K}{2}\right\rfloor + 1\right) \geq N$$
where $N$ is a given integer $> 1$.
I tried with
$$K = \left\lfloor 2(\sqrt{N} - 1)\right\rfloor,$$
but it does not seem really correct in general. Can you explain how I can properly get the correct formula?
 [/INST] Say we have a positive integer $K$ such that
$$\left(K - \left\lfloor\frac{K}{2}\right\rfloor + 1\right)\left(\left\lfloor\frac{K}{2}\right\rfloor + 1\right) \geqslant N.\tag{1}$$
Now, if $K = 2m$ is even, $(1)$ means $$(m+1)^2 \geqslant N \iff m \geqslant \sqrt{N} - 1 \iff K \geqslant 2(\sqrt{N}-1),$$ and since $K$ is an integer, that is equivalent to $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$.
If $K = 2m-1$ is odd, $(1)$ means that $$(m+1)m \geqslant N \iff 4m^2 + 4m + 1 > 4N \iff (2m+1) > 2\sqrt{N} \iff K > 2(\sqrt{N}-1),$$ and since $K$ is an integer, that implies $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$.
So whether $K$ is even or odd, $(1)$ implies that $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$, and it only remains to show that
$$S := \lceil 2(\sqrt{N}-1)\rceil\tag{2}$$
satisfies $(1)$ (with $K$ substituted by $S$). From $(2)$ follows
$$2(\sqrt{N}-1) \leqslant S \iff \sqrt{N}-1 \leqslant \frac{S}{2} .$$
If $S$ is even, we immediately obtain $\left(\frac{S}{2}+1\right)^2 \geqslant N$, and if $S$ is odd, we obtain
$$\left(\frac{S+1}{2}+1\right)\left(\frac{S-1}{2}+1\right) \geqslant \left(\sqrt{N}+\frac12\right)\left(\sqrt{N}-\frac12\right) = N - \frac14.$$
But the left hand side is an integer, hence $\left(\frac{S+1}{2}+1\right)\left(\frac{S-1}{2}+1\right) \geqslant N.$
</s>