16
$\begingroup$

When working on improving my skills with indices, I came across the following question:

Find the smallest positive integers $m$ and $n$ for which: $12<2^{m/n}<13$

On my first attempt, I split this into two parts and then using logarithms found the two values $m/n$ had to be between. However I wasn't sure how to progress past that.

I have the answer itself $(11/3)$, but I'm unsure of the best method to find it. Any help would be really appreciated.

$\endgroup$
29
$\begingroup$

The inequality is equivalent to $\,12^n \lt 2^m \lt 13^n\,$. By brute force, looking for powers of $2$ between $12^n$ and $13^n$ starting from the lowest possible $n=1$ up:

  • $\;n=1\,$: no solutions, since $\,2^3 = 8 \lt 12^1 \lt 13^1 \lt 16=2^4\,$

  • $\;n=2\,$: no solutions, since $\,2^7 = 128 \lt 144 = 12^2 \lt 13^2 = 169 \lt 256=2^8\,$

  • $\;n=3\,$: $\,12^3 = 1728 \lt 2048 = 2^{11} \lt 2197 = 13^3\,$, therefore $m=11, n=3$ is a solution.

$\endgroup$
  • 2
    $\begingroup$ Isn't this what the OP did? Brute force after simplifying? I thought the question was is this the best method or is there a better method. . . doesn't answer that at all. $\endgroup$ – iheanyi Jul 5 '17 at 19:33
  • 5
    $\begingroup$ @iheanyi The OP used logarithms to determine that $\log_2 12 \lt m/n \lt \log_2 13\,$ numerically. My answer does not use logarithms, but only simple calculations that can be easily done by hand. $\endgroup$ – dxiv Jul 5 '17 at 20:23
  • $\begingroup$ Ah, I see. Though I'm not really sure hand calculations is much of an improvement. Once I've used a calculator to determine $log_2 12$ and $log_2 13$, wouldn't I then need to use your method to determine the candidate m and n? $\endgroup$ – iheanyi Jul 5 '17 at 23:36
  • $\begingroup$ And I can answer my own question - "yes", which is why this is an answer to how to proceed beyond "that" where that was the work the OP did using logarithms. Thanks for following up. $\endgroup$ – iheanyi Jul 5 '17 at 23:39
  • 1
    $\begingroup$ I only specified "your method" to indicate that I'd seen the error of my original comment. $\endgroup$ – iheanyi Jul 6 '17 at 0:07
14
$\begingroup$

Starting with $12^n < 2^m < 13^n$, we see that $n \log_2(12) < m < n \log_2(13)$. We conclude that \begin{align} m &= \left\lceil n\dfrac{\log(12)}{\log(2)} \right\rceil \\ &\approx \lceil n \times 3.584962500721156181453738943947816508759814407692481060455\dots \rceil \end{align}

The first few values of $m$ and $n$ are

$(m,n) \in \{(11, 3), (15, 4), (18, 5), (22, 6), (26, 7), (29, 8), (33, 9), (36, 10)\}$

You can see that $m=11$ and $n=3$ will be the smallest values of $m$ and $n$.

Note also that there is no smallest value of $\dfrac mn$ since $\displaystyle \lim_{n \to \infty} \dfrac mn = \log_2 12$ and $\log_2 12$ is irrational.

$\endgroup$
8
$\begingroup$

From $2^{\frac{m}{n}}<13$ follows $\dfrac{m}{n}<\log_2{13}$

Developing $\log_2{13}$ in continued fraction we get $\{3,1,2,2,1,\ldots\}$

Using $3+\dfrac{1}{1+\dfrac{1}{2}}$ we get $\dfrac{11}{3}$ which gives $m=11;\;n=3$

Going on we find $3+\dfrac{1}{1+\frac{1}{2+\frac{1}{2}}}=\dfrac{26}{7}$ which gives $m=26;\;n=7$ and so on

$\endgroup$
3
$\begingroup$

$$3.5849...=\log_{2}12<\frac{m}{n}<\log_{2}13=3.70...$$ Thus, for $\frac{m}{n}=3\frac{2}{3}$ it occurs.

If we want to make $3$ in the denominator be smaller than we'll get $n=2$ and it's impossible.

Thus, $3\frac{2}{3}=\frac{11}{3}$ is our answer.

$\endgroup$
  • 1
    $\begingroup$ Yes, using the interval from $3.5849\ldots$ to $3.7004\ldots$ comes close to the approach the asker talked about. Then trying with $n=1$, we have the whole numbers (integers), and none of them falls within the interval. Then with $n=2$, we get all the multiples of one half, but still none is inside the interval ($3+\frac12$ is too low, and $4$ is too high). Then with $n=3$, we have "everything with thirds", and we find the solution you describe. This gives a very explicit explanation of why that solution is the minimal one. $\endgroup$ – Jeppe Stig Nielsen Jul 6 '17 at 11:18
1
$\begingroup$

You can write this as an integer program:

$ \text{min } m + n$

subject to:

$n \log_2(12) - m <= 0$

$n \log_2(13) - m >= 0$

$m >= 1$

$n >= 1$

and solve with an integer programming solver. This might suffer from numerical issues.

$\endgroup$
  • $\begingroup$ Rather than minimizing $m+n$, consider minimizing $z$ where $m \le z$ and $n \le z$. $\endgroup$ – Théophile Jul 5 '17 at 15:30
  • $\begingroup$ Why not an AI approach: depth first search with iterative deepening of the depth bounds? $\endgroup$ – richard1941 Jul 12 '17 at 0:20
0
$\begingroup$

First, move the constants around. \begin{align*} 12 &< 2^{m/n} < 13 \\ \ln 12 &< \dfrac{m}{n} \ln 2 < \ln 13 \\ \log_2 12 &< \dfrac{m}{n} < \log_2 13 \\ n \log_2 12 &< m < n \log_2 13 \\ \end{align*} Note that this shows that $m$ and $n$ are minimized together (since $m$ is bounded by constant multiples of $n$).

The last line shows we are guaranteed to have a solution if $n (\log_2 13 - \log_2 12) \geq 1$. (Any interval of length at least $1$ contains at least one integer.) This says there is a choice of $m$ for all $n \geq \dfrac{1}{\log_2 13 - \log_2 12} = 8.659\dots$. An exhaustive search will find a solution for $n = 9$ and may have found one for a smaller $n$. Since $9$ is not a very big number, exhaustive search is feasible.

But we can do better. Note that $2^3 = 8 < 12 < 13 < 16 = 2^4$, so $m/n \in (3,4)$. Write $m = 3n + m'$ so that $0 < m' < n$ and then \begin{align*} 0.584 \ldots = \log_2 12/8 < \dfrac{m'}{n} < \log_2 13/8 = 0.700\dots \end{align*} From here, we only need to check which $n$, when multiplied by $\log_2 13/8$ have a new integer part, then check to see whether $\log_2 12/8$ was left far enough behind. (A way to do this efficiently is to use Bresenham's line algorithm for finding where the integer part increments.) We get this table: \begin{align*} n && \lfloor \log_2 &13/8 \rfloor & \lfloor \log_2 &12/8 \rfloor \\ 1 && 0 && 0 \\ 2 && 1 && 1 \\ 3 && 2 && 1 \end{align*} and we're done. We read that $n=3$ allows $m'=2$ and then $m = 3\cdot 3 + 2 = 11$.

But suppose we weren't done. The table would continue \begin{align*} 4 && 2 && - \\ 5 && 3 && 2 \\ 6 && 4 && 3 \\ 7 && 4 && - \\ 8 && 5 && 4 \\ 9 && 6 && 5 \end{align*} where we stop when we hit $n=9$, which is guaranteed to have a solution. Notice, there is no reason to find the value in the 3rd column when the integer part in the second column has not increased.

Note that we can actually calculate the multiples of $\log_2 13/8 = 0.700 \dots$ "by eye", so the only work in this particular problem is the integer part of the multiples of $\log_2 12/8$.

$\endgroup$
  • $\begingroup$ Calculation of log to base 2 is easy in floating point. A crude approximation is to write a dot, then the mantissa portion of the floating pint representation. If you have a decimal number between 1 and 2, just subtract 1. It is exact for 1 and 2, and a bit low at the middle of the interval. For more on logs, see Doerfler's wonderful book. $\endgroup$ – richard1941 Jul 12 '17 at 0:26
0
$\begingroup$

$12 \lt 2^{m/n} \lt 13$

$\log_2 12 \lt \frac{m}{n} \lt \log_2 13$

$[3; 1, 1, 2, 2, \dots] \lt \frac{m}{n} \lt [3; 1, 2, 2, 1, \dots]$

The continued fractions match up to $[3; 1]$. Since $[3; 1, 1]$ and $[3; 1, 2]$ are underestimations of $\log_2 12$ and $\log_2 13$, we take $[3; 1, 1]$ (the "smaller" one lexicographically) and add $1$ to the last number (round "up"), so the answer is $[3; 1, 2]$.

$[3; 1, 2]=3+\frac{1}{1+\frac{1}{2}}=3+\frac{1}{\frac{3}{2}}=3+\frac{2}{3}=\frac{11}{3}$

So $m=11$, $n=3$.

This works for all nonnegative bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.