1248136

Andy's little brother is playing a game with the list of powers of 2 : 2: 1 , 2 , 4 , 8 , 16 , 32 , 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 8 , then he writes down the first digits of 8, 16 and 32, which gives 813. 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.

2 solutions

Mark Hennings
Sep 23, 2013

The following table shows the possible different leading digits of 2 x 2x , given the leading digit of x x : x 2 x 1 2 , 3 2 4 , 5 3 6 , 7 4 8 , 9 5 , 6 , 7 , 8 , 9 1 \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 124 , 125 125 , 136 136 , 137 137 , 248 248 , 249 249 , 251 251 , 361 361 , 371 371 , 481 481 , 491 491 , 512 512 , 513 513 , 612 612 , 613 613 , 712 712 , 713 713 , 812 812 , 813 813 , 912 912 , 913 913 of possible three digit numbers.

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

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

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

Nice solution!

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

Alexander Borisov - 7 years, 8 months ago

Log in to reply

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

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

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

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

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

Alexander Borisov - 7 years, 8 months ago

Log in to reply

@Alexander Borisov Obviously. For any irrational number α > 0 \alpha>0 and positive real numbers 0 < c < d 0 < c < d we can find positive integers n , a n,a such that c < α n a < d c < \alpha n - a < d . Use α = log 2 \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 ) (d-c) ). Then taking multiples of that means going around the interval [ 0 , 1 ) [0,1) in small steps. So we are not going to miss the interval ( c , d ) . (c,d). And irrationality of log 2 \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 α n a \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 { α x y : x , y \{|\alpha|x-y:x,y positive integers } \} .

Peter Byers - 7 years, 8 months ago

Log in to reply

@Peter Byers

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 N<0 is the supremum of negative elements, and P > 0 P>0 is the infimum of positive elements. Then there exist elements n , p n,p such that:

N P < n N N-P<n\le N

P p < P N P\le p<P-N

which means N < p + n < P 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 R \mathbb{R} other than { 0 } \{0\} either has a minimum positive element, or else is dense in R \mathbb{R} . A subgroup of R \mathbb{R} generated by 1 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 2^n is to have first digit 2 2 , it must equal x × 1 0 a x \times 10^a in standard form, where 2 x < 3 2 \le x < 3 . Since I want the leading digit of 2 n + 1 2^{n+1} to be 4 4 , not 5 5 , I must have 2 x < 2.5 2 \le x < 2.5 (so that 4 2 x < 5 4 \le 2x < 5 ). Finally, since I want the leading digit of 2 n + 2 2^{n+2} to be 9 9 , not 8 8 , I must have 2.25 x < 2.5 2.25 \le x < 2.5 , so that 4.5 2 x < 5 4.5 \le 2x < 5 and hence 9 4 x < 10 9 \le 4x < 10 . The expression to obtain 713 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 2^n tends to infinity, the last three digits (which I will refer to as x n x_n ) divided by 100 100 will be in every range ( n 4 , n + 1 4 ) \left(\dfrac{n}{4}, \dfrac{n+1}{4} \right) where n n is an integer between 4 4 and 39 39 inclusive.

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

k k 2 k 4 k 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 \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 6 rows (whose first elements are 1 2.25 1 \longrightarrow 2.25 ) represent distinct x n x_n . The next 10 10 rows (whose first elements are 2.5 4.75 2.5 \longrightarrow 4.75 ) produce a new x n x_n every 2 2 rows, for 5 5 new x n x_n . The next 8 8 rows (whose first elements are 5 6.75 5 \longrightarrow 6.75 ) produce a new x n x_n every 4 4 rows, for 2 2 new x n x_n . The next 4 4 rows (whose first elements are 7 7.75 7 \longrightarrow 7.75 ) produce a new x n x_n every 2 2 rows for 2 2 new x n x_n . The last 8 8 rows (whose first elements are 8 9.75 8 \longrightarrow 9.75 ) produce a new x n x_n every 4 4 rows for 2 2 new x n x_n .

This is a total of 17 17 x n x_n .

Trevor B. - 7 years, 8 months ago

Log in to reply

Yes, this works too.

Alexander Borisov - 7 years, 8 months ago

12481361251248136125124813612512481361251248137125124913712512491371251249137136124913713612491371361251248136 First ten found in this pattern: 1248136125 With digit 7: 137, 371, 712, 713 With digit 9: 249, 491, 913

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

A Brilliant Member - 7 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...