1
$\begingroup$

How do I find the minimum integer value of 'n' for the inequality $\frac{n^2 - n}{2} >= m$, where $m$ is an integer $> 0$.

I would like to get some pointers on solving such problems in general, not necessarily a specific answer to the above question, that works algorithmically as well. How do I go about this?

$\endgroup$
3
$\begingroup$

One way to approach this is to rewrite it as $n^2-n-2m\ge 0$. The graph of $y=x^2-x-2m$ is a parabola opening up, with $x$-intercepts at

$$x=\frac{1\pm\sqrt{1+8m}}2\;,$$

so $x^2-x-2m\ge 0$ when $x\le\frac12(1-\sqrt{1+8m})$ and when $x\ge\frac12(1+\sqrt{1+8m})$. You are therefore seeking the smallest integer $n$ such that $n\ge\frac12(1+\sqrt{1+8m})$.

Here we were fortunate: the inequality is only quadratic, so we can easily solve it; in general that may be difficult or impossible in closed form, though numerical methods are always available to find approximate solutions, and that’s good enough when we want the smallest or largest integer for which it holds.

By the way, there’s an even shorter approach to this specific problem: $n$ and $n-1$ are consecutive integers whose product is $2m$, so they must be the two integers nearest to $\sqrt{2m}$, one larger and the other smaller. Thus, $n=\lceil\sqrt{2m}\rceil$.

$\endgroup$
4
  • $\begingroup$ Thanks Brian. But using that approximation, for sufficiently large values of $m$ in the range of $10^{18}$, the actual correct solution is far away from what the result gives? $\endgroup$
    – Navneeth G
    Sep 10 '13 at 3:16
  • $\begingroup$ @Navneeth: I’m not sure what you mean: both solutions to the specific problem yield exact answers. Perhaps you’re not familiar with the ceiling function? $\endgroup$ Sep 10 '13 at 3:18
  • $\begingroup$ Yes Brian, I am familiar with the ceiling operation. Let me just check on that. Thanks. $\endgroup$
    – Navneeth G
    Sep 10 '13 at 3:23
  • $\begingroup$ @Navneeth: You’re welcome. $\endgroup$ Sep 10 '13 at 3:26

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.