I don't know of an analytical solution (I don't believe there is one -- if there is, please correct me). The solution depends on the value of k as follows:
For k<0, there is exactly one solution for x, 0<x<1.
For 0<=k<e, there is no solution
For k=e, we simply have x=e.
For k>e, there are two solutions for x. Plot x/ln(x) on a graph and use numerical methods to find them.
I'm not a real math guy, but I believe you solve these with a technique called asymptotic iteration. So for sufficiently large k you can assign an initial guess at x (which I label x0). Then plug that into the original and repeat:
x = k * ln x
for large k (and x):
x0 = k
x1 = k * ln k (plugging in x0 in for x)
x2 = k * ln (k * ln k) (plugging in x1 for x, etc...)
x3 = k * ln (k * ln (k * ln k))
x4 = k * ln (k * ln (k * ln (k * ln k)))
x5 = k * ln (k * ln (k * ln (k * ln (k * ln k))))
As this technique is asymptotic you can determine the error as it decreases with each iteration (usually just denoted as a big O of some small function). I tried this with k = 30 and the values of x I calculated were:
30, 102.03, 138.75, 147.98, 149.91, 150.30 respectively. To double check... 150.30/ln(150.30) = 29.9845.
Actually that helps a lot. I was writing a basic Sieve of Eratosthenes to generate prime numbers, and was using that equation to estimate an upper bound on the size of the sieve array if looking for at least k primes.
Or more simply, if I wanted at least k primes, x would be a loose upper bound on the numbers I would have to look at.
So in short, approximation is good enough. I wrote the following to implement it:
def approximate(k, times)
return k if times < 1
return k * Math.log(approximate(k, times - 1))
end
For values of k I am looking at (1E4 up to 1E9), recursing 10 times approximated to within 0.01 of the actual value, which is definitely good enough for what I need.
Thanks everyone for your replies. I'd still be interested in an exact answer, but at least this solves today's problem.
I don't think there is an exact analytical solution. Of course if you're only interested in the first d decimal points you can just rearrange the terms so the piece you're inserting the recurrence in is less than 10^-d for very large k (around what you'll be using). IIRC this is also the only way to solve problems in form x*e^(x) = k. The rearrange of terms is trivial in that case. I think it might be harder in this case.
Yeah I got it to the x^k = e^x form, but that is where I got stuck. I was just hoping there was some trick to pull at that point that I couldn't remember, but extensive review of my logarithm/exponent rules was getting me nowhere.
Yes, this is not correct. This would would mean x asymptotically approaches e as k increases. However, if k = 30, x should be nearly 150. See my other post for more details.
For k<0, there is exactly one solution for x, 0<x<1.
For 0<=k<e, there is no solution
For k=e, we simply have x=e.
For k>e, there are two solutions for x. Plot x/ln(x) on a graph and use numerical methods to find them.