# $n=8\log_2(n)$, forgot basic math

I'm quite ashamed that I'm at a math-related course at the university and I'm stuck. I can't solve at all this equation: $$n=8\log_2(n).$$

I have tried applying the log property so it becomes $2^n = 2^{8n}$.

Besides that this didn't help me, I'm not even sure if I applied right the property that says $x=\log_2(y) \Rightarrow 2^x=y$

-
You can write down a solution using Lambert's W function (see my answer), but there is no elementary solution. –  Arturo Magidin Apr 7 '11 at 15:40
Is the actual problem to find the natural number where $2^n$ becomes greater? –  Aryabhata Apr 7 '11 at 16:29
could be, yes, there still would be no analytical way to solve it, right? –  Clash Apr 7 '11 at 21:35
The Lambert function is considered an analytic solution. Functions are invented and given a notation when they show up a lot in applications, and people find them useful. That's all there is to it. –  Guess who it is. Apr 10 '11 at 5:26

1. No, you didn't apply it correctly. Since $8\log_2(n) = \log_2(n^8)$, what you have is equivalent to $n=\log_2(n^8)$, or $2^n = n^8$. Equivalently, by taking $8$th roots, $2^{n/8} = n$, which can also be obtained by writing the original equation as $\frac{n}{8} = \log_2(n)$.

2. The reason you are having trouble is that there is no elementary solution. You can write a solution using Lambert's W function. The $W$ function has the property that $W(z)=x$ if and only if $z=xe^x$.

To use Lambert's $W$ function, we can proceed as follows: let $u=\frac{n}{8}$. Then: \begin{align*} n &= 2^{n/8}\\ 8u &= 2^u\\ \frac{8u}{2^u} &= 1\\ 1 &= 8ue^{-u\ln(2)}\\ \frac{1}{8} &= ue^{-u\ln(2)}\\ \frac{-\ln 2}{8} &= -u\ln(2)e^{-u\ln(2)}\\ W\left(-\frac{\ln 2}{8}\right) &= -u\ln(2)\\ u &= -\frac{1}{\ln(2)}W\left(-\frac{\ln 2}{8}\right)\\ \frac{n}{8} &= -\frac{1}{\ln(2)}W\left(-\frac{\ln 2}{8}\right)\\ n &= -\frac{8}{\ln 2}W\left(-\frac{\ln 2}{8}\right). \end{align*}

Added. Note that Lambert's $W$ function on the reals is "double valued" on $(-\frac{1}{e},0)$. Since $-\frac{\ln 2}{8}$ lies in this interval, this actually gives you two values for $n$.

Remark. I certainly wouldn't call Lambert's W function "basic math"; so let's say you got a bit confused with the logarithm properties and then ran into a big brick wall (which most people running this direction run into the first time, before they are told about the secret passage to go under it), rather than saying you "forgot basic math"...

-
Holy c***! Thanks. I'm not doing my bachelor in Math, I'm actually studying computer science and before I did half of the course of electrical engineering and I had never heard of Lambert's W, so I suppose I won't need it. But good to know such thing exists for this kind of equation. Thanks again, I'm going to give the answer for someone else that answered first. I will upvote you when I have 15 creds. Thanks again for the long answer! –  Clash Apr 7 '11 at 15:45
Yes Arturo, you are right, I'm happy to know that this is no basic math! I just thought the book would always give me stuff to solve that was elementary, that's why I thought it was basic math and that I had forgotten something important... luckly I was wrong and this book is just evil! –  Clash Apr 7 '11 at 15:48
I'm confused. The Wikipedia link you gave for the W func says $z=W(z)e^{W(z)}$ is the defining equation and asserts that $W(e)=1$. But in your answer you say that $W(x)=z$ iff $z=xe^x$ which implies $W(1)=e$, an inverse of the Wikipedia def. –  Fixee Apr 7 '11 at 16:04
@Fixee: I just screwed up; the definition is that $z=W(z)e^{W(z)}$, so that means that $W(z)=x$ if and only if $z=xe^x$. I'll fix it, and thanks! –  Arturo Magidin Apr 7 '11 at 17:21
@Clash: You're supposed to accept the best answer, not the first one, so to help guide readers to it. In fact it's better not to accept answers for a few days to give everyone a chance to see the question, and to keep the thread alive. And you can always change your accepted answer. –  Bill Dubuque Apr 8 '11 at 3:25

It should be $2^{n/8}=n \implies 2^n=n^8$. Which cannot be solved analytically. Then you may want to use numerical methods to solve it.

-
To whoever downvoted, please let me know why. –  picakhu Apr 7 '11 at 15:10
Before applying numerical methods you should at least ask topic starter to verify how many roots there are. –  Ilya Apr 7 '11 at 15:13
I do not understand your comment. –  picakhu Apr 7 '11 at 15:14
You advised to use numerical methods for the solution. Before applying it you should know how many solutions there are - otherwise numerical methods will say nothing to you. –  Ilya Apr 7 '11 at 15:16
Your solution does not show the number of roots either. It claims it is 2. –  picakhu Apr 7 '11 at 15:19

You made a mistake. After applying $2^\cdot$ to both sides you obtain $2^n = n^8$. There will be two positive roots (you don't need negative because $n$ have to be positive since it is an argument of the logarithm).

There are two positive roots due to the fact that on $[0,1.1]$ $2^n>n^8$ but the derivative of $n^8$ is greater - so at approx. $n_1 = 1.1$ there is the first intersection. On the other hand exponential function grows faster then any power function and there will be the second root $n_2 \approx 43.5$. After this root the exponential function $2^n$ will be greater than $n^8$ as well as its derivative will be greater than the derivative of the power function for all $n>n_2$ hence there will no be more roots.

Edited: There is no integer solution for an equation $100n^2 = 2^n$ since the left-hand side will never be a power of $2$ - the same for the rationals. On the other hand you can always use LambertW function which is defined as a solution of such equations (as it was mentioned in the answer which is deleted now).

Due to the same reasons there will be two roots which you can find numerically.

-
Thanks, this is what I wanted to know. I feel better now that there is no analytical way to solve it. I was afraid I had forgotten too much. I did notice my mistake a couple minutes later though, which is also good. By the way, I don't way to make a new question. I suppose 100*n^2=2^n also has no analytical solution? Thanks again –  Clash Apr 7 '11 at 15:32
I've edited my answer to cover your 2nd question. –  Ilya Apr 7 '11 at 15:37
It really depends on what you call an analytic solution. you can use the product log function to get analytic solutions. reference.wolfram.com/mathematica/ref/ProductLog.html –  picakhu Apr 7 '11 at 15:37
Yeah, I prefer to say that there is no roots in a closed form (like simple functions). Once you know that some equation has only one root you can always define a function which is a solution of this equation and say that you found analytical solution. –  Ilya Apr 7 '11 at 15:40

This is hard to solve because there are no elementary manipulations that will convert this into a form you can use. That is, solving for $n$:

$$2^n = n^8$$

is not a problem that is reasonable to be solved in a pre-calc or calculus type class.

In fact, there is a symbolic solution to this, but it's sorta cheating. Suppose you have a function $W(x)$ such that

$$y = W(x) e^{W(x)}$$

(This is called the Lambert W Function )

then you can use $W$, with suitable algebraic manipulation, to help solve weird relations like yours (um...Arturo did this for you so thankfully I won't have to bother now).

Then you can use numerical properties of $W$ to get actual values.

The cheating part is because you just assume there's a solution function of a certain form $W$ with its properties) and manipulate your original problem to reduce to using $W$ (as Arturo did). And then, because other people have done lots of numerical analysis on $W$, you can (using tables or a computer algebra system like Maple or Mathmatica) get a numerical answer.

But if all you care about is a symbolic answer, you can stop at Arturo's.

Which is all to say, you shouldn't be ashamed at all, the equation you have is not solvable with the tools you have at your disposal.

-
I don't really understand the mentality that the Lambert function is "cheating"... it's a bit akin to saying that methods for drawing a segment of length $\sqrt[3]{2}$ are "cheating" because they don't use straightedge/compass. –  Guess who it is. Apr 10 '11 at 5:25
...another tack: functions themselves are human inventions, not something "natural". If something shows up a lot in work, it is probably a good idea to name it. –  Guess who it is. Apr 10 '11 at 5:29
@J.M.: Your cube root idea is right but not because of the straightedge/compass reason but because presumably if all you have is addition and multiplication, taking roots is somewhat inscrutable (you can't just use a finite set operations to calculate it exactly). The equation above can't be done in elementary functions, so you create a new function $W$ in which you can. For the purposes of a homework it might be considered 'not really solving the problem'. –  Mitch Apr 10 '11 at 13:38
My point is that the objection that the Lambert function is a "cheat" is psychological, not mathematical. –  Guess who it is. Apr 10 '11 at 14:51
@J.M.: Yes, but isn't it all psychological at some point? Plus and times need to implemented numerically eventually, but we psychologically think of them as given, but $W$ we don't. –  Mitch Apr 10 '11 at 14:55

As other answers stated, there is no closed-form solution (and using Lambert's W function is cheating as Mitch said, but there's no other useful approach). Using Arturo's answer with WolframAlpha, we can approximate the two real solutions to $2^n = n^8$:

1.099997030237609400896029066804951287873546345878742213371636137380943292069214386133076258825375517822416342887670093802580...

and

43.559260436881656413950762048860950275727905818177002096841114348332640315621743543500535784941726303460441430049628636723144...

So Gortaur's approximations were very good. Since you're a computer science major, perhaps the prof wanted you to compute these numbers?! It's not hard to binary search for them (and there are other ways that converge faster).

-
Oh he didn't want me to compute it. These two functions are how much time it takes to do a certain algorithm. The book wanted to know when one was better than the other –  Clash Apr 7 '11 at 21:34
@Clash: Then you simply want to show that the growth rate of $2^n$ is higher than $n^8$. You can do this from the definition of $O()$, and you certainly don't need Lambert's W function. –  Fixee Apr 7 '11 at 22:33
But he wanted to know when 2^n is worser than n^8 –  Clash Apr 8 '11 at 6:45
The best way to do this is write a 10-line program to find the cross-over point: n=2; while (1) { if 2^n > n^8: {print n; exit;} else n++;}. Since the answer is 44, this would run in < 1 msec. –  Fixee Apr 8 '11 at 16:41