Associated Topics || Dr. Math Home || Search Dr. Math

Powers of Two

```
Date: 05/29/97 at 12:40:17
From: Jose A. Cofre
Subject: Number theory ?

I will be participating in the 36th annual school mathematics
competition.I have a sample question and I am totally stumped:

Prove that every power of 2 has a multiple whose decimal expansion has
only digits 1 and 2.  For example, 3*2^2 = 12 and 14*2^3 = 112.

I have considered that 2^2, 2^3, 2^4... make a geometric sequence, so
I have used the formula for the nth term of a geometric progression:
Tn = ar^n-1, where a is the first term and r is the common ratio.
So my equation is: ar^n-1*(integer) = ?  I don't know if this is
correct, but I don't even know how to describe the decimal expansion
with digits only 1 and 2.

Thank for helping me,
Joe
```

```
Date: 05/29/97 at 17:41:47
From: Doctor Wilkinson
Subject: Re: Number theory ?

Dear Joe,

This is a cute problem!

I think you're best off trying to prove it by induction.  As you
noticed:

2 is a multiple of 2
12 is a multiple of 4
112 is a multiple of 8

I seem to be able to continue this:

2112 is a multiple of 16
22112 is a multiple of 32

So it seems as if I can just keep tacking digits on on the left, okay?
That is, I don't seem to have to scramble up the digits I've already
got to get up to the next power of 2.  Let's see if we can prove that
this will work.

Suppose we have a k-digit number consisting of just 1's and 2's which
is divisible by 2^k.  We want to tack a 1 or a 2 on to the left to get
a number that's divisible by 2^(k+1).

Now 10^k is divisible by 2^k, so 2*10^k is divisible by 2^(k+1).
If the k-digit number is already divisible not only by 2^k but by
2^(k+1), we can add a 2 on the left and get a number that will be
divisble by 2^(k+1).

The other possibility is that the k-digit number is divisible by 2^k
but not by 2^(k+1).  That means that when we divide it by 2^k we get
an odd number, so it's of the form:

2^k (2x + 1)

What happens if we add a 1 on the left?  That adds 10^k, so we
have:

10^k + 2^k (2x + 1) =
10^k + 2^(k+1) x + 2^k =

2^(k+1) x + 2^k * 5^k + 2^k =

2^(k+1) x + 2^k (5^k + 1)

5^k + 1 is even, so it's of the form 2y and we have:

2^(k+1) x + 2^k (2y) = 2^(k+1) + 2^(k+1) y,

which is a multiple of 2^(k+1) and we have succeeded!

-Doctor Wilkinson,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search