1

I am trying to solve the same problem as asked here.

In short, I am trying to find the values for which $$8n^2 \lt 64n\,\log_2(n)$$

To find a solution in the real numbers, it involves using the Lambert W function, but as the domain of the functions is limited to the natural numbers this answer suggests "do it numerically".

If this means plugging integers into the two functions and finding the values for which the inequality holds, how should I approach the selection of the integers?

How can I tackle this problem more efficiently than just picking numbers from the air?

Community
  • 1
jsj
  • 535

3 Answers3

3

Simplify $$\tag08n^2<64n\log_2 n$$ to $$\tag1n<8\log_2 n.$$ As the logarithm has sublinear growst, there are at most finitely many $n$ that satisfy $(1)$. More precisely, the derivative of the left hand side in $(1)$ is $1$, that of the right hand side is $ \frac{8}{n\ln 2}$. As this is $<1$ if $n>\frac 8{\ln 2}\approx11.5$ and $>1$ if $n<\frac8{\ln2}$, we expect that $(1)$ holds precisely for $n_1\le n\le n_2$ with integers $n_1<11.5$ and $n_2>11-5$ yet to be determined.

Finding $n_1$ is easy: We see that $(0)$ is not satisfied for $n=0$ (right hand side not defined or $=0$, it's a matter of taste), $n=1$ ($8\not<0$), but is satisfied for $n=2$ ($32<128$). Hence $n_1=2$.

Now we look for $n_2$, which turns out to be a bit larger. If we substitute $n=2^\alpha$ with $\alpha\in\mathbb R_{\ge0}$, then $(1)$ becomes $2^\alpha<2^3\alpha$ or $$\tag2 2^{\alpha-3}<\alpha.$$ This suggests to start trying at $\alpha=3$ where $(2)$ says $1<3$; next, $\alpha=4$ yields $2<4$ - still true; then $\alpha=5$ yields $4<5$ - still true; but the fourth try $\alpha=6$ yields $8\not<6$. So we should check for values of $n$ between $n=2^5=32$ (true) and $n=2^6=64$ (false), for example using binary search. This lets us find (e.g. after testing $n=48$, $n=44$, $n=42$, $n=43$) that the upper limit for $n$ implied by $(0)$ is $n\le n_2=43$.

In summary: $$ 8n^2<64n\log_2n\iff 2\le n\le 43.$$

Hagen von Eitzen
  • 374,180
  • By what principle do the derivatives imply that $n_1\le n\le n_2$? Could you perhaps elaborate on that step? – jsj Mar 09 '13 at 15:05
2

Dividing through by $8n$ yields $n\lt8\log_2n$

Since $\log_2n$ is roughly the number of binary digits of $n$, this is fulfilled for small $n$ and not for large $n$. It seems easier to find the boundary if we transform to $n=2^k$, which yields $2^k\lt8k$. This is fulfilled for $k=5$ but not for $k=6$. Then binary search between $32$ and $64$ finds that $48$ is too high, $40$ is too low, $44$ is too high, $42$ is too low and $43$ is too low, so the inequality is satisfied up to and including $n=43$.

Alternatively, since $\log_2n$ changes slowly, start with some $n$ and iterate:

$$ \begin{array}{c|c} n&\lceil8\log_2n\rceil\\\hline 2&8\\ 8&24\\ 24&37\\ 37&42\\ 42&44\\ 44&44 \end{array} $$

joriki
  • 238,052
0

After reducing the problem to the simplest form $$ \frac18n < \log_2n$$ I would plot the two functions $f(x)=x$ and $g(x)=8\log_2x$ on the same plane (you may assume positive $x$ values, of course).
You observe that for $x<1$ the logarithm is negative and that the two functions are both monotonically increasing, but the logarithm grows slower. So there will be a limit value $x=x_0$ such that $f(x)>g(x)\quad \forall x>x_0$.

So you conclude that you are looking for a single interval of values (you may restrict yourself to the integers) between the two points of intersection of $f$ and $g$.

This for a reasonable qualitative analysis. Then you plug in specific values for $x$, or $n$. But not randomly!

Andrea Orta
  • 1,122