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?

  • $\begingroup$ Wow beautiful. thanks for the edit Zev! $\endgroup$ – Pam Jul 9 '13 at 18:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Zev Chonoles Jul 9 '13 at 18:40
  • 1
    $\begingroup$ You need the ceiling, not the floor. $\endgroup$ – Daniel Fischer Jul 9 '13 at 18:53
  • $\begingroup$ Sure ? Would that not conflict with the case we restricted to even integers only (in which case my attempt above should be correct) ? $\endgroup$ – Pam Jul 9 '13 at 19:18
  • 1
    $\begingroup$ @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). $\endgroup$ – coffeemath Jul 9 '13 at 20:54

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.