The Vault: Powers of two

My new book of maths puzzles is on its way! It’s packed full of interesting problems to sink your teeth into. I’ll post an update as the launch approaches.

In the meantime, here is a fantastic problem from the USA:

It is given that 2^{2004} is a 604-digit number beginning with a 1. How many of the numbers 2^0, 2^1, 2^2, 2^3, ..., 2^{2003} begin with a 4?

On the face of it, the fact that this can even be solved in a reasonable length of time is astonishing. There are so many numbers in that list! And yet, the solution is remarkably simple.

The first idea is to consider how the first digit of a number changes when you double the number. After some thought, we arrive at the following possible ‘first digit chains’:

1,2,4,8,1…

1,2,4,9,1,…

1,2,5,1,…

1,3,6,1,…

1,3,7,1,…

Notice that we keep coming back to a first digit of 1, whatever other first digits appear in the chain. But the crucial observation is that the digit 4 appears precisely in the long chains, and never in the short chains.

So, in moving through the powers of 2 from 2^0 to 2^{2003}, the first digits appear in blocks of length four (1,2,4,8,… or 1,2,4,9,…) or length three (1,2,5,… or 1,3,6, … or 1,3,7,…). Furthermore, the number of times the first digit 4 appears is equal to the number of chains of length four.

But all this information can be summarised in one pair of equations! If we let x and y be the number of four-chains and three-chains respectively, then we have

x+y=603 (since every chain represents an increase of one digit in the length of the number )

and

4x+3y=2004 (since there are 2004 terms from 1 to $2^{2003}$.

Solving simultaneously yields x=195, so the number of terms beginning with the digit 4 is 195.

The problem is utterly brilliant. I’ve seen many questions in which one has to form their own simultaneous equations, but rarely have I seen one of such creative invention.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s