12
$\begingroup$

Is this statement true?

Between any two consecutive powers of $5$, there are either two or three powers of $2$.

I can see that this statement is true for cases like $$5^1 < 2^3 < 2^4 < 5^2$$ or $$5^3 < 2^7 < 2^8 < 2^9 < 5^4$$

But I am having a trouble figuring out the proof through generalization.

Could somebody help me?

$\endgroup$
22
$\begingroup$

How many integer multiples of $\log_5(2)$ can we fit between the integers $n$ and $n+1$? It's not too hard to see that since $\log_5(2)<0.5$, there are at least $2$ such numbers. But, since $3\log_5(2)>1$, there are at at most $3$ such numbers. *

So then, if $n$ and $n+1$ straddled $2$ multiples, we would have (for an appropriate integer, $k$): $$n<k\log_5(2)<(k+1)\log_5(2)<n+1\\\Rightarrow5^n<2^k<2^{k+1}<5^{n+1}$$ Conversely, if $3$ multiples were straddled, we would have $$n<k\log_5(2)<(k+1)\log_5(2)<(k+2)\log_5(2)<n+1\\\Rightarrow5^n<2^k<2^{k+1}<2^{k+2}<5^{n+1}$$

Therefore there are between $2$ and $3$ powers of $2$ between each successive powers of $5$.


* To visualise this, consider the figure below. The red points are multiples of $\log_5(2)$. The distance between the red points ($\approx0.43$) is small enough to guarantee that at least $2$ of them lie between the black points. However the gap between $4$ red points ($\approx1.29$) is too wide to fit between the black points. This is irrespective of where the red points begin.

enter image description here

Here's a fun graph to play around with https://www.desmos.com/calculator/qfqers5mmg. No matter where you start the sequence of red points (by varying the parameter $h$), you inevitably have either $2$ or $3$ red points between the black points.

$\endgroup$
9
$\begingroup$

Basically, it boils down to the fact that $5$ is between $2^2 = 4$ and $2^3 = 8$. Here's a proof, though.

Let $5^a$ and $5^{a+1}$ be the two consecutive powers of $5$. Let $2^b$ be the smallest power of $2$ that exceeds $5^a,$ and $2^c$ the largest below $5^{a+1}$.

Then we have $2^{b-1} \leq 5^a < 2^b$ and $2^c < 5^{a+1} \leq 2^{c+1}$.

From this we get $$\frac{2^{c}}{2^{b}} < \frac{5^{a+1}}{5^a} \leq \frac{2^{c+1}}{2^{b-1}} $$ or, equivalently, $$2^{c-b} < 5 \leq 4 \cdot 2^{c-b}.$$

This inequality can be rewritten as $ \frac{5}{4} \leq 2^{c-b} < 5$, which proves that $c - b$ is either $1$ or $2$. Thus the powers of $2$ between $5^a$ and $5^{a+1}$ are either $2^b, 2^{b+1} = 2^c$, or $2^b, 2^{b+1}, 2^{b+2} = 2^c.$ This is what you wanted.

$\endgroup$
6
$\begingroup$

We can see mathematically that there is a ratio between the number of powers of $2$ and the number of powers of $5$ below a certain integer $a$.

Intuitively, the ratio would be $\log_25$, or $2.32$. On average, for every power of $5$, you get $2.32$ powers of $2$. That would translate to about $2$ or $3$ powers of $2$ between every two powers of $5$.

If this isn't completely intuitive, notice that there are exactly $3$ more powers of $2$ than $8$, as $\log_28 = 3$. For example, out of all integers below $100$, there are $6$ powers of $2$ ($2,4,8,16,32,64$) and $2$ powers of $8$ ($8,64$).

We can extend to this to any integers $x$ and $y$, provided they are not $0$ or $1$: For all integers below an integer $z$, the ratio of the number of exponents of $a$ to the number of exponents of $b$ is $\log_ab$.

$\endgroup$
4
$\begingroup$

In the special case $[1,5]$, we see that 1, 2 and 4 are in the interval but 8 and up are not. There are powers of 2 less than and powers of two greater than any other power of 5.

There can't be more than three, because if $0 < a \leq b < 2b < 4b < 8b \leq 5a$, we get the contradiction $8a \leq 5a$ for a positive number $a$.

Nor can there be zero, because if $0 < b < a < 5a < 4b$, we get the contradiction $5b < 4b$ for a positive number b.

Nor can there be one, because the argument still holds if we insert the condition $a \leq 2b \leq 5a$.

You already found existence proofs for two or three intermediate powers.

The explanations in the other answers are great, but that's a very elementary proof.

$\endgroup$
  • $\begingroup$ Hi, @Davislor. Sorry but I don't quite follow where $8a\leq 5a$ comes from - it seems as though you've replaced the $b$ that was previously in the inequality but how is this justified? $\endgroup$ – Jam Jul 26 '18 at 20:09
  • 1
    $\begingroup$ @Jam $0< a \leq b$, so $8a \leq 8b$. Bit, we assumed $8b \leq 5a$. Thus the contradiction that $8a \leq 5a$ for positive $a$. $\endgroup$ – Davislor Jul 26 '18 at 20:15
  • $\begingroup$ @Jam: Do you find my elementary proof any clearer? $\endgroup$ – Ilmari Karonen Jul 27 '18 at 10:33
  • $\begingroup$ @IlmariKaronen I find both quite clear, thanks - I was just stuck on one step in Davislor's :) $\endgroup$ – Jam Jul 27 '18 at 11:04
2
$\begingroup$

It's easy enough to see that this is indeed true, even without using logarithms.

Let $a$ be some power of $5$, and let $b$ be the least power of $2$ not less than $a$. Then the next power of $5$ after $a$ is obviously $5a$, while the next three powers of $2$ after $b$ are $2b$, $4b$ and $8b$.

Since, by definition, $a \le b$, it follows that $5a \le 5b < 8b$. Thus, there can be at most three powers of $2$ ($b$, $2b$ and $4b$) between $a$ and $5a$.

Conversely, since $b$ is the least power of $2$ not less than $a$, it follows that $\frac12 b < a$. Thus, equivalently, $2b < 4a < 5a$, so there must be at least two powers of $2$ ($b$ and $2b$) between $a$ and $5a$.


BTW, if you look closely at the proof above, you may note that it doesn't actually use the assumption that $a$ is a power of $5$ anywhere. Thus, in fact, we've proven a more general result: for any positive number $a$, there are either two or three powers of $2$ between $a$ and $5a$.

(In fact, the proof doesn't really use the assumption that $b$ is a power of $2$, either, so we could generalize the result even further in this direction if we wanted!)

Also, you may notice that the key observation behind the result above is that the number $5$ lies strictly between $2^2 = 4$ and $2^3$ = 8. Thus, by essentially the same logic as above, we can prove a similar result for other bases:

Between any two consecutive powers of $x$ there are at least $k$ and at most $k+1$ powers of $y$, where $x$ and $y$ are any numbers greater than $1$, and $k$ is the largest integer such that $y^k \le x$.

$\endgroup$
1
$\begingroup$

We know that

if $y-x >1$, for $x\geq 0, y>0$, then there $\exists n \in \mathbb{N}, n>0$ s.t. $$x<n<y \tag{1}$$

e.g. $n=\left \lfloor x \right \rfloor+1$, because $$x = \left \lfloor x \right \rfloor+\{x\}<\left \lfloor x \right \rfloor+1<x+1<y$$ In this case $$(k+1)\frac{\ln{5}}{\ln{2}}-k\frac{\ln{5}}{\ln{2}}=\frac{\ln{5}}{\ln{2}}>1$$ and from $(1)$, there $\exists n\in\mathbb{N}$ s.t. $$k\frac{\ln{5}}{\ln{2}}<n<(k+1)\frac{\ln{5}}{\ln{2}} \iff\\ k\ln{5}<n\ln{2}<(k+1)\ln{5} \iff \\ 5^k < 2^n<5^{k+1}$$ However $\frac{\ln{5}}{\ln{2}}\approx 2.32>2$ and $(1)$ can be extended to

if $y-x >2$, for $x\geq 0, y>0$, then there $\exists n \in \mathbb{N},n>0$ s.t. $$x<n<n+1<y \tag{2}$$

$\endgroup$

Your Answer

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