Ask YC: Help Me With A Math Problem | Hacker News Reader

Ask YC: Help Me With A Math Problem

5 pointsXichekolas13 comments

I hate to admit it, but my math is a bit rusty. Can someone show me how to solve the following equation for x?

k = x/(ln x)

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.

Hope this helps.

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.

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.

Clearest way I see. Is to look at the equivalent form: x^k = e^x. Then aneesh's solutions seem obvious.

I don't believe there's an analytic solution either. Otherwise it'd be in my CRC as x/ln(x) crops up quite a bit.

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.

http://en.wikipedia.org/wiki/Lambert's_W_function

This seems related.

now, i might be wrong, but i managed to simplify it down to:

x= exp(k/(k-1))

my math is definitely rusty. be kind. (and i don't have my calculator)

edit: as pointed out by the comments, i'm wrong.

I think you might be mistaken...e.g., plugging in k=0 yields x=e, but if you put x=e in the original equation, you get k=e.

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.

What do you mean, solve it? There's nothing to solve for since we don't know whether k is a constant or what..

I would presume k is a constant.

I mean solving for x in terms of k. I know k and want x.

Reply on news.ycombinator.com