Smallest Possible Power

Question

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.

Answer 1

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.

Answer 2

$$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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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$.

Answer 7

$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.