How do I solve $2^x + x = n$ equation for $x$?

Question

I need to solve the equation $$2^x + x = n$$ for $x$ through a programming-based method. Is this possible? If not, then what would be the most efficient way to approximate it?

Answer 1

You could either use numerical methods such as interval bisection, Newtons Method of finding roots applied to $f(x) = 2^x + x - n$, as in Winther's solution.

Secondly, you could solve this equation manually to get the solutions as $x=0$ for $n=1$ and $$x=n-\frac{W_{c}\left(2^n \ln 2\right)}{\ln 2}$$ where we let $c$ range over the integers. If you are utilising a language (Mathematica, let's say) that has the Lambert W function built in, you could simply iterate the function by running through $c \in \mathbb{Z}$.

Note:
If you're looking for real solutions, $W_0(x)$ is real for $−1/e\leq x<\infty$ and $W_{−1}(x)$ is real for $−1/e\leq x < 0$. The other branches do not have real values on $\mathbb{R}$. In this case, we have $2^n \ln 2 > 0$, so we only need $W_0$. (Thanks to Robert Israel)

Answer 2

Newton's method is usually the best numerical method for such problems: it's very simple, converges very fast and it works most of the time.

To use it define a function $f(x) = 2^x +x - n$ so that the desired solution to your problem is the solution to $f(x) = 0$. Pick a guess $x_0$, say $x_0 = 0$, and the itterate via

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

For example if $n=10$ and $x_0 = 0$ then after only $7$ itterations you have the solution to $10$ significant digits. As a convergence criterion you can for example use $|f(x_n)| < \epsilon$ where $\epsilon$ is some small predefined constant.

---

${\bf More~above~the~convergence~criterion~in~general}$:

There are many ways to do the convergence criterion and depending on the problem at hand one will be better than the other. Here are some options.

As Claude mentioned below for some functions $|f|$ itself might be unaturally small far away from the desired solution so that monitoring the smallness of $|f(x_n)|$ is not advisable. One cn get around this be considering a criterion like $|x_n - x_{n-1}| < \epsilon$.

Another option is the following: after making the initial guess we first perform $N$ itterations (a 'burn-in') and calculate the initial residual $|f(x_N)|$. Then we continue itterating and define convergence when $\frac{|f(x_k)|}{|f(x_{N}|} < \epsilon$.

One can also consider a combination of $|f(x_k)|$ and $|x_n-x_{n-1}|$ as the criterion. The best advise here is to experiment with the problem-type you have at hand to see for your self what works best.

Answer 3

As Winther answered, Newton method is probably the simplest numerical method to use.

When you look at the function $$f(x) = 2^x +x - n$$ you should notice that it is quite stiff. But, changing to $$g(x)=x \log(2)-\log(n-x)$$ makes the function quite linear.

Uisng the same case as Winther $n=10$ and starting at $x_0=0$, the iterates are $$x_1=2.903099386$$ $$x_2=2.840013526$$ $$x_3=2.839966365$$ which is the solution for $10$ significant digits.

Let us make it (apparently) more difficult with $n=10^6$ still starting at $x_0=0$; the iterates are $$x_1=19.93153981$$ which is the solution for $10$ significant digits.

In practice, you can use as a starting point the first iterate of Newton method that is to say $$x_0=\frac{\log (n)}{\frac{1}{n}+\log (2)}$$

You could have a better approximation using Halley method which leads to $$x_0=\frac{n \left(2 (n \log (2)+1)^2-\log (n)\right) \log (n)}{2 (n \log (2)+1)^3}$$ For $n=10$, this would give $x_0\approx 2.84997$.

Answer 4

A possibly efficient method: deriving with respect to $n$, you get the differential equation

$$\frac{dx}{dn}(\ln(2)2^x+1)=1,$$

or $$\frac{dx}{dn}=\frac1{ln(2)(n-x)+1}.$$

Using a fixed-step integration method (Runge-Kutta) with step $1$ will give you the $x_n$. (Preferably combined with a step of Newton to avoid drift.)