Cómo encontrar el menor número entero positivo $K$ tal que $(K -\lfloor\frac{K}{2}\rfloor + 1)(\lfloor\frac{K}{2}\rfloor + 1) \geq N$

Question

Estoy escribiendo un programa y necesitaría una fórmula explícita para lo siguiente:

El menor número entero positivo $K$ tal que:

$$\left(K - \left\lfloor\frac{K}{2}\right\rfloor + 1\right)\left(\left\lfloor\frac{K}{2}\right\rfloor + 1\right) \geq N$$

donde $N$ es un número entero dado $> 1$ .

Lo intenté con $$K = \left\lfloor 2(\sqrt{N} - 1)\right\rfloor,$$ pero no parece realmente correcto en general. ¿Puede explicar cómo puedo obtener la fórmula correcta?

Answer 1

Digamos que tenemos un número entero positivo $K$ tal que

$$\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}$$

Ahora bien, si $K = 2m$ está en paz, $(1)$ significa $$(m+1)^2 \geqslant N \iff m \geqslant \sqrt{N} - 1 \iff K \geqslant 2(\sqrt{N}-1),$$ y como $K$ es un número entero, que equivale a $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$ .

Si $K = 2m-1$ es impar, $(1)$ significa que $$(m+1)m \geqslant N \iff 4m^2 + 4m + 1 > 4N \iff (2m+1) > 2\sqrt{N} \iff K > 2(\sqrt{N}-1),$$ y como $K$ es un número entero, lo que implica que $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$ .

Así que si $K$ es par o impar, $(1)$ implica que $K \geqslant \lceil 2(\sqrt{N}-1)\rceil$ y sólo queda demostrar que

$$S := \lceil 2(\sqrt{N}-1)\rceil\tag{2}$$

satisface $(1)$ (con $K$ sustituido por $S$ ). En $(2)$ sigue

$$2(\sqrt{N}-1) \leqslant S \iff \sqrt{N}-1 \leqslant \frac{S}{2} .$$

Si $S$ es par, obtenemos inmediatamente $\left(\frac{S}{2}+1\right)^2 \geqslant N$ y si $S$ es impar, obtenemos

$$\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.$$

Pero el lado izquierdo es un número entero, por lo tanto $\left(\frac{S+1}{2}+1\right)\left(\frac{S-1}{2}+1\right) \geqslant N.$