Andy's little brother is playing a game with the list of powers of 2 : 1 , 2 , 4 , 8 , 1 6 , 3 2 , … 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 8 1 3 .
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 1 7 cases are possible without "looking at first hundred powers of 2 "?
Log in to reply
You start with 1 , 1 2 8 , 1 6 , 2 , 2 5 6 , 3 2 , 4 0 9 6 , 5 1 2 , 6 4 , 8 1 9 2 to obtain the numbers 1 2 4 , 1 2 5 , 1 3 6 , 2 4 8 , 2 5 1 , 3 6 1 , 4 8 1 , 5 1 2 , 6 1 2 , 8 1 3 respectively. This just leaves 1 3 7 , 2 4 9 , 3 7 1 , 4 9 1 , 7 1 2 , 7 1 3 and 9 1 3 to find.
If we can obtain 1 3 7 by starting with 2 n , we must obtain 3 7 1 by starting with 2 n + 1 (and one of 7 1 2 or 7 1 3 next). If we can obtain 2 4 9 by starting with 2 n , we must obtain 4 9 1 by starting with 2 n + 1 and then obtain 9 1 3 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 1 3 7 , 2 4 9 , 7 1 2 and 7 1 3 explicity.
To find the number 1 3 7 , we need to find positive integers a , n such that 1 . 7 5 × 1 0 a ≤ 2 n < 2 × 1 0 a in which case we obtain 1 3 7 by starting with 2 n . These inequalities reduce to finding a , n such that lo g 2 lo g 1 . 7 5 + a ≤ n < 1 + lo g 2 a The smallest value of a for which this is possible is a = 1 3 , with n = 4 4 . Starting with 2 4 4 , we obtain the number 1 3 7 . Then starting with 2 4 5 we obtain the number 3 7 1 , and starting with 2 4 6 we obtain the number 7 1 2 .
To find the number 2 4 9 , we need to find positive integers a , n such that 2 . 2 5 × 1 0 a ≤ 2 n < 2 . 5 × 1 0 a in which case we obtain the number 2 4 9 by starting with 2 n . These inequalities reduce to requiring lo g 2 lo g 2 . 2 5 + a ≤ n < lo g 2 lo g 2 . 5 + a The smallest value of a for which this is true is a = 1 5 , with n = 5 1 . Then starting with 2 5 1 yields the number 2 4 9 .
Finally, to find the number 7 1 3 , we need to find positive integers a , n such that 7 . 5 × 2 a ≤ 2 n < 8 × 2 a in which case we obtain the number 7 1 3 by starting with 2 n . These inequalities reduce to lo g 2 lo g 7 . 5 + a ≤ n < lo g 2 lo g 8 + a The smallest value of a for which this is true is a = 2 8 , with n = 9 6 . Thus starting with 2 9 6 yields the number 7 1 3 .
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.
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.
Log in to reply
@Alexander Borisov – Obviously. For any irrational number α > 0 and positive real numbers 0 < c < d we can find positive integers n , a such that c < α n − a < d . Use α = lo g 2 .
This is quite a big result to throw around without a proof, and my previous posts were long enough!
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 α 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 lo g 2 is also quite obvious (assuming uniqueness of prime decomposition for integers).
Log in to reply
@Alexander Borisov – Or you could consider every other convergent in the continued fraction expansion of α . This would ensure that α n − a was always positive, and would give you an upper bound on the size of the integers needed.
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 – 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 positive integers } .
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 ≤ N
P ≤ p < P − N
which means N < p + n < P , which contradicts the assumptions.)
Log in to reply
@Peter Byers – Any additive subgroup of R other than { 0 } either has a minimum positive element, or else is dense in R . A subgroup of R generated by 1 and an irrational is of the second type.
how did you write the expression to find the number 249 and713
Log in to reply
@Anurag Nayan – If 2 n is to have first digit 2 , it must equal x × 1 0 a in standard form, where 2 ≤ x < 3 . Since I want the leading digit of 2 n + 1 to be 4 , not 5 , I must have 2 ≤ x < 2 . 5 (so that 4 ≤ 2 x < 5 ). Finally, since I want the leading digit of 2 n + 2 to be 9 , not 8 , I must have 2 . 2 5 ≤ x < 2 . 5 , so that 4 . 5 ≤ 2 x < 5 and hence 9 ≤ 4 x < 1 0 . The expression to obtain 7 1 3 is obtained similarly.
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"
Log in to reply
Try the other posts found here. About four different approaches to the proof are given.
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 1 0 0 will be in every range ( 4 n , 4 n + 1 ) where n is an integer between 4 and 3 9 inclusive.
Using this information, I made this chart, where k = 4 n .
k k 1 1 . 2 5 1 . 5 1 . 7 5 2 2 . 2 5 2 . 5 2 . 7 5 3 3 . 2 5 3 . 5 3 . 7 5 4 4 . 2 5 4 . 5 4 . 7 5 5 5 . 2 5 5 . 5 5 . 7 5 6 6 . 2 5 6 . 5 6 . 7 5 7 7 . 2 5 7 . 5 7 . 7 5 8 8 . 2 5 8 . 5 8 . 7 5 9 9 . 2 5 9 . 5 9 . 7 5 2 k 2 2 . 5 3 3 . 5 4 4 . 5 5 5 . 5 6 6 . 5 7 7 . 5 8 8 . 5 9 9 . 5 1 0 1 0 . 5 1 1 1 1 . 5 1 2 1 2 . 5 1 3 1 3 . 5 1 4 1 4 . 5 1 5 1 5 . 5 1 6 1 6 . 5 1 7 1 7 . 5 1 8 1 8 . 5 1 9 1 9 . 5 4 k 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9
In this chart, the first 6 rows (whose first elements are 1 ⟶ 2 . 2 5 ) represent distinct x n . The next 1 0 rows (whose first elements are 2 . 5 ⟶ 4 . 7 5 ) produce a new x n every 2 rows, for 5 new x n . The next 8 rows (whose first elements are 5 ⟶ 6 . 7 5 ) produce a new x n every 4 rows, for 2 new x n . The next 4 rows (whose first elements are 7 ⟶ 7 . 7 5 ) produce a new x n every 2 rows for 2 new x n . The last 8 rows (whose first elements are 8 ⟶ 9 . 7 5 ) produce a new x n every 4 rows for 2 new x n .
This is a total of 1 7 x n .
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!
Problem Loading...
Note Loading...
Set Loading...
The following table shows the possible different leading digits of 2 x , given the leading digit of x : x 1 2 3 4 5 , 6 , 7 , 8 , 9 2 x 2 , 3 4 , 5 6 , 7 8 , 9 1 We are immediately restricted to the list 1 2 4 , 1 2 5 , 1 3 6 , 1 3 7 , 2 4 8 , 2 4 9 , 2 5 1 , 3 6 1 , 3 7 1 , 4 8 1 , 4 9 1 , 5 1 2 , 5 1 3 , 6 1 2 , 6 1 3 , 7 1 2 , 7 1 3 , 8 1 2 , 8 1 3 , 9 1 2 , 9 1 3 of possible three digit numbers.
However, if the leading digit of x is either 5 or 6 , then 5 × 1 0 a ≤ x < 7 × 1 0 a for some integer a ≥ 0 , so that 1 × 1 0 a + 1 ≤ 2 x < 1 . 4 × 1 0 a + 1 and 2 × 1 0 a + 1 ≤ 4 x < 2 . 8 × 1 0 a + 1 . Thus if x has leading digit 5 or 6 , then 2 x has leading digit 1 and 4 x has leading digit 2 . Thus the numbers 5 1 3 and 6 1 3 are not possible.
Similarly, if the leading digit of x is either 8 or 9 , then 8 × 1 0 a ≤ x < 1 × 1 0 a + 1 for some integer a ≥ 0 , so that 1 . 6 × 1 0 a + 1 ≤ 2 x < 2 × 1 0 a + 1 and hence 3 . 2 × 1 0 a + 1 ≤ 4 x < 4 × 1 0 a + 1 . Thus the leading digit of 2 x is 1 and the leading digit of 4 x is 3 . Thus the numbers 8 1 2 and 9 1 2 are not possible.
Looking at the first hundred powers of 2 quickly shows us that the other 1 7 numbers are all possible. Thus there is a total of 1 7 possible three-digit numbers that can be written down.