4 ms·

Ask YC: Help Me With A Math Problem

• deleted 19y ago
  [deleted]
• aneesh 19y ago
  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.
• henning 19y ago
  What do you mean, solve it? There's nothing to solve for since we don't know whether k is a constant or what..
  • aneesh 19y ago
    I would presume k is a constant.
  • Xichekolas 19y ago
    I mean solving for x in terms of k. I know k and want x.
• dnaquin 19y ago
  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.
  • Xichekolas 19y ago
    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.
• noodle 19y ago
  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.
  • apu 19y ago
    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.
  • brent 19y ago
    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.
• brent 19y ago
  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.
  • Xichekolas 19y ago
    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.
    • brent 19y ago
      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.
• yelsgib 19y ago
  http://en.wikipedia.org/wiki/Lambert's_W_function http://en.wikipedia.org/wiki/Lambert's_W_function This seems related.