# 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?

• Wow beautiful. thanks for the edit Zev! – Pam Jul 9 '13 at 18:39
• No problem, glad to help! You can see here for a guide to writing math with MathJax, and see here for a guide to formatting posts with Markdown. – Zev Chonoles Jul 9 '13 at 18:40
• You need the ceiling, not the floor. – Daniel Fischer Jul 9 '13 at 18:53
• Sure ? Would that not conflict with the case we restricted to even integers only (in which case my attempt above should be correct) ? – Pam Jul 9 '13 at 19:18
• @Pam It would seem ceiling is what you need, since you want the left side to be greater than or equal to $n$. Also I just checked out that it works for ceiling in a lot of cases (didn't prove that). – coffeemath Jul 9 '13 at 20:54

## 1 Answer

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