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.
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.
Hope this helps.