Andy's little brother is playing a game with the list of powers of $2:$ $1,2,4,8,16,32, \ldots$ He chooses randomly one of the powers and then writes down a three-digit number made out of its first digit, then the first digit of the next number, then the first digit of the next number. How many possible different three-digit numbers can he write down?

**
Details and assumptions
**

As an explicit example, if Andy's brother chooses number $8$ , then he writes down the first digits of 8, 16 and 32, which gives $813.$

The answer is 17.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Nice solution!

Can you prove that all $17$ cases are possible without "looking at first hundred powers of $2$ "?

Alexander Borisov
- 7 years, 8 months ago

Log in to reply

You start with $1$ , $128$ , $16$ , $2$ , $256$ , $32$ , $4096$ , $512$ , $64$ , $8192$ to obtain the numbers $124$ , $125$ , $136$ , $248$ , $251$ , $361$ , $481$ , $512$ , $612$ , $813$ respectively. This just leaves $137$ , $249$ , $371$ , $491$ , $712$ , $713$ and $913$ to find.

If we can obtain $137$ by starting with $2^n$ , we must obtain $371$ by starting with $2^{n+1}$ (and one of $712$ or $713$ next). If we can obtain $249$ by starting with $2^n$ , we must obtain $491$ by starting with $2^{n+1}$ and then obtain $913$ by starting with $2^{n+2}$ . Thus finding three of these numbers follows from finding the others, and so we are left with having to find $137$ , $249$ , $712$ and $713$ explicity.

To find the number $137$ , we need to find positive integers $a,n$ such that $1.75 \times 10^a \le 2^n < 2\times10^a$ in which case we obtain $137$ by starting with $2^n$ . These inequalities reduce to finding $a,n$ such that $\frac{\log1.75 + a}{\log 2} \le n < 1 + \frac{a}{\log 2}$ The smallest value of $a$ for which this is possible is $a=13$ , with $n=44$ . Starting with $2^{44}$ , we obtain the number $137$ . Then starting with $2^{45}$ we obtain the number $371$ , and starting with $2^{46}$ we obtain the number $712$ .

To find the number $249$ , we need to find positive integers $a,n$ such that $2.25 \times 10^a \le 2^n < 2.5 \times 10^a$ in which case we obtain the number $249$ by starting with $2^n$ . These inequalities reduce to requiring $\frac{\log2.25 + a}{\log 2} \le n < \frac{\log2.5 + a}{\log 2}$ The smallest value of $a$ for which this is true is $a=15$ , with $n=51$ . Then starting with $2^{51}$ yields the number $249$ .

Finally, to find the number $713$ , we need to find positive integers $a,n$ such that $7.5 \times 2^a \le 2^n < 8 \times 2^a$ in which case we obtain the number $713$ by starting with $2^n$ . These inequalities reduce to $\frac{\log7.5 + a}{\log 2} \le n < \frac{\log8 + a}{\log 2}$ The smallest value of $a$ for which this is true is $a=28$ , with $n=96$ . Thus starting with $2^{96}$ yields the number $713$ .

Thus we can obtain all the other numbers. Whether this argument is much more informative than plugging the following two lines into Mathematica:

```
a[n_] := IntegerDigits[2^n][[1]]*100 +
IntegerDigits[2^(n + 1)][[1]]*10 + IntegerDigits[2^(n + 2)][[1]]
DeleteDuplicates[Sort[Table[a[n], {n, 0, 99}]]]
```

is moot.

Mark Hennings
- 7 years, 8 months ago

Log in to reply

Yes, I definitely agree: to actually find the consecutive powers with the respective first digits, looking at the first 100 powers of 2 with a computer is most probably the best approach. However, one can prove that the solutions exist (without actually finding them) without using a computer. Basically, one can use your second argument, but then instead of finding the smallest $a,$ prove that it exists.

Alexander Borisov
- 7 years, 8 months ago

Log in to reply

@Alexander Borisov – Obviously. For any irrational number $\alpha>0$ and positive real numbers $0 < c < d$ we can find positive integers $n,a$ such that $c < \alpha n - a < d$ . Use $\alpha=\log2$ .

This is quite a big result to throw around without a proof, and my previous posts were long enough!

Mark Hennings
- 7 years, 8 months ago

Log in to reply

@Mark Hennings – Yes, thank you for the detailed proof. (And you have posted quite a few excellent proofs on this forum)!

The theorem you quote is actually fairly easy to prove. First, one can find by the Dirichlet Box Principle some positive multiple of $\alpha$ very close to an integer (within $(d-c)$ ). Then taking multiples of that means going around the interval $[0,1)$ in small steps. So we are not going to miss the interval $(c,d).$ And irrationality of $\log 2$ is also quite obvious (assuming uniqueness of prime decomposition for integers).

Alexander Borisov
- 7 years, 8 months ago

Log in to reply

@Alexander Borisov – Or you could consider every other convergent in the continued fraction expansion of $\alpha$ . This would ensure that $\alpha n - a$ was always positive, and would give you an upper bound on the size of the integers needed.

Mark Hennings
- 7 years, 8 months ago

Log in to reply

@Mark Hennings – Yes, indeed, the continued fraction theory is ultimately the sharpest tool for this type of questions, in dimension one (i.e. no simultaneous approximations). Alas, like all meaningful theories, it cannot be really explained in a couple of paragraphs.

Alexander Borisov
- 7 years, 8 months ago

@Alexander Borisov – Or another way to look at is that any set that contains both positive and negative real numbers and is closed under addition, must contain zero or numbers arbitrarily close to it. Apply this to the set $\{|\alpha|x-y:x,y$ positive integers $\}$ .

Peter Byers
- 7 years, 8 months ago

Log in to reply

any set that contains both positive and negative real numbers and is closed under addition, must contain zero or numbers arbitrarily close to it.

(Suppose not. That is, suppose that zero isn't an element, and $N<0$ is the supremum of negative elements, and $P>0$ is the infimum of positive elements. Then there exist elements $n,p$ such that:

$N-P<n\le N$

$P\le p<P-N$

which means $N<p+n<P$ , which contradicts the assumptions.)

Peter Byers
- 7 years, 8 months ago

Log in to reply

@Peter Byers – Any additive subgroup of $\mathbb{R}$ other than $\{0\}$ either has a minimum positive element, or else is dense in $\mathbb{R}$ . A subgroup of $\mathbb{R}$ generated by $1$ and an irrational is of the second type.

Mark Hennings
- 7 years, 8 months ago

how did you write the expression to find the number 249 and713

Anurag Nayan
- 7 years, 8 months ago

Log in to reply

@Anurag Nayan – If $2^n$ is to have first digit $2$ , it must equal $x \times 10^a$ in standard form, where $2 \le x < 3$ . Since I want the leading digit of $2^{n+1}$ to be $4$ , not $5$ , I must have $2 \le x < 2.5$ (so that $4 \le 2x < 5$ ). Finally, since I want the leading digit of $2^{n+2}$ to be $9$ , not $8$ , I must have $2.25 \le x < 2.5$ , so that $4.5 \le 2x < 5$ and hence $9 \le 4x < 10$ . The expression to obtain $713$ is obtained similarly.

Mark Hennings
- 7 years, 8 months ago

Yea, that's what I want to know too. I didn't post my solution (even though I wrote one) because I didn't have a justification for those 17 other than "I checked to see if they exist, and they do"

Michael Tong
- 7 years, 8 months ago

Log in to reply

Try the other posts found here. About four different approaches to the proof are given.

Mark Hennings
- 7 years, 8 months ago

I did something really similar to this. As $2^n$ tends to infinity, the last three digits (which I will refer to as $x_n$ ) divided by $100$ will be in every range $\left(\dfrac{n}{4}, \dfrac{n+1}{4} \right)$ where $n$ is an integer between $4$ and $39$ inclusive.

Using this information, I made this chart, where $k=\dfrac{n}{4}$ .

$\begin{array}{c}kk & 2k & 4k\\ 1 & 2 & 4\\ 1.25 & 2.5 & 5\\ 1.5 & 3 & 6\\ 1.75 & 3.5 & 7\\ 2 & 4 & 8\\ 2.25 & 4.5 & 9\\ 2.5 & 5 & 10\\ 2.75 & 5.5 & 11\\ 3 & 6 & 12\\ 3.25 & 6.5 & 13\\ 3.5 & 7 & 14\\ 3.75 & 7.5 & 15\\ 4 & 8 & 16\\ 4.25 & 8.5 & 17\\ 4.5 & 9 & 18\\ 4.75 & 9.5 & 19\\ 5 & 10 & 20\\ 5.25 & 10.5 & 21\\ 5.5 & 11 & 22\\ 5.75 & 11.5 & 23\\ 6 & 12 & 24\\ 6.25 & 12.5 & 25\\ 6.5 & 13 & 26\\ 6.75 & 13.5 & 27\\ 7 & 14 & 28\\ 7.25 & 14.5 & 29\\ 7.5 & 15 & 30\\ 7.75 & 15.5 & 31\\ 8 & 16 & 32\\ 8.25 & 16.5 & 33\\ 8.5 & 17 & 34\\ 8.75 & 17.5 & 35\\ 9 & 18 & 36\\ 9.25 & 18.5 & 37\\ 9.5 & 19 & 38\\ 9.75 & 19.5 & 39\\ \end{array}$

In this chart, the first $6$ rows (whose first elements are $1 \longrightarrow 2.25$ ) represent distinct $x_n$ . The next $10$ rows (whose first elements are $2.5 \longrightarrow 4.75$ ) produce a new $x_n$ every $2$ rows, for $5$ new $x_n$ . The next $8$ rows (whose first elements are $5 \longrightarrow 6.75$ ) produce a new $x_n$ every $4$ rows, for $2$ new $x_n$ . The next $4$ rows (whose first elements are $7 \longrightarrow 7.75$ ) produce a new $x_n$ every $2$ rows for $2$ new $x_n$ . The last $8$ rows (whose first elements are $8 \longrightarrow 9.75$ ) produce a new $x_n$ every $4$ rows for $2$ new $x_n$ .

This is a total of $17$ $x_n$ .

Trevor B.
- 7 years, 8 months ago

4 Helpful
0 Interesting
0 Brilliant
0 Confused

What did you do? Hats off if you calculated them manually!

A Brilliant Member
- 7 years, 8 months ago

×

Problem Loading...

Note Loading...

Set Loading...

The following table shows the possible different leading digits of $2x$ , given the leading digit of $x$ : $\begin{array}{|c|c|} \hline \mathbf{x} & \mathbf{2x} \\ \hline 1 & 2,3 \\ 2 & 4,5 \\ 3 & 6,7 \\ 4 & 8,9 \\ 5,6,7,8,9 & 1 \\ \hline \end{array}$ We are immediately restricted to the list $124$ , $125$ , $136$ , $137$ , $248$ , $249$ , $251$ , $361$ , $371$ , $481$ , $491$ , $512$ , $513$ , $612$ , $613$ , $712$ , $713$ , $812$ , $813$ , $912$ , $913$ of possible three digit numbers.

However, if the leading digit of $x$ is either $5$ or $6$ , then $5\times10^a \le x < 7\times10^a$ for some integer $a \ge 0$ , so that $1\times10^{a+1} \le 2x < 1.4 \times10^{a+1}$ and $2\times10^{a+1} \le 4x < 2.8 \times 10^{a+1}$ . Thus if $x$ has leading digit $5$ or $6$ , then $2x$ has leading digit $1$ and $4x$ has leading digit $2$ . Thus the numbers $513$ and $613$ are not possible.

Similarly, if the leading digit of $x$ is either $8$ or $9$ , then $8\times 10^a \le x < 1\times10^{a+1}$ for some integer $a \ge 0$ , so that $1.6\times10^{a+1} \le 2x < 2 \times 10^{a+1}$ and hence $3.2 \times 10^{a+1} \le 4x < 4\times 10^{a+1}$ . Thus the leading digit of $2x$ is $1$ and the leading digit of $4x$ is $3$ . Thus the numbers $812$ and $912$ are not possible.

Looking at the first hundred powers of $2$ quickly shows us that the other $17$ numbers are all possible. Thus there is a total of $17$ possible three-digit numbers that can be written down.