1
$\begingroup$

I found this interesting problem in a programming forum. It would be great to get some help..

Solve for $K$,

$K-1 \leq 27\cdot\log_{10}(9(K-1)) $

We plotted it to find that $K\leq77$. Can you solve this one using paper and pencil?

Thanks!

2 Answers 2

2

In general, I imagine there is no easy solution. In this case, you can determine some bounds, although I'm not sure I could consider this any less 'brute force' than just evaluating the expression.

Let $f(x) = x-1-27\cdot\log_{10}(9(x-1))$. $f$ is defined on $(1,\infty)$. You are looking for integers in $(1,\infty)$ that satisfy $f(x) \leq 0$, hence we may restrict our attention to $[2,\infty)$.

Differentiating $f$ gives $f'(x) = 1-\frac{27}{(x-1)\ln 10}$, and $f''(x) = \frac{27}{(x-1)^2\ln 10}$, hence $f$ is strictly convex on $[2,\infty)$, and $\lim_{x\to \infty} f(x) = + \infty$.

Solving $f'(x_{min}) = 0$ yields $x_{min} = 1+\frac{27}{\ln 10} \approx 12.7$. Since $f(2) < 0$, we have that $f$ is strictly decreasing on $[2,12]$, and strictly increasing (to $\infty$) on $[13, \infty)$ (it is easy to check that $f(13) < 0$). Hence we know that $f(x) = 0$ has a unique solution on $[13,\infty)$, denote this unique solution by $\hat{x}$.

Since $f$ is strictly convex and $\lim_{x\to \infty} f(x) = + \infty$, using Newton's method to solve $f(x) = 0$, starting at $x_0 = 13$, will produce a sequence $x_n$ of iterates that satisfy $x_n \geq \hat{x}$ (for $n> 0$), and $x_{n+1} \leq x_n$. Furthermore, these iterates will converge quadratically (ie, very quickly) to the solution. It is easy to check that $x_4 \approx 77.6$, and since $f(77) < 0$ and $f(78) > 0$, this means that the integer solutions to $f(x) \leq 0$ are $\{2,...,77\}$.

2

You can actually go a bit higher than 77, I think there is no exact way to solve this, you must use numerical approximation. A quick play around with google calculator gives $K \leq 77.645721$ to 6 decimal places.

  • 0
    Well the thing is...we might not be able to find it explicitly. There is no guarantee that the solution is some specially defined number. I cannot find a way to get a closed form solution, but maybe others on here might be able to. If not then we have to make do with approximations.2012-06-22