Proof with Powers of 2 and a Product

Date: 10/22/2008 at 17:59:08
From: Off
Subject: Any power of 2 can be multiplied with result digits 1 2 only

I need to prove that for any power of 2 there is a number that when 
you multiply the two you get a number with digits 1 and 2 only.  For
example:

4*3 = 12
8*14 = 112
64*33 = 2112

Thank you,

Off 

Date: 10/24/2008 at 22:52:34
From: Doctor Vogler
Subject: Re: Any power of 2 can be multiplied with result digits 1 2 only

Hi,

Thanks for writing to Dr. Math.  That's an interesting question.  I
would start with the final digits, since if you have the n'th power of
2 (that is, 2^n), then the last n digits are determined.  So I would
argue that there is an infinite sequence a_n with

  a_1 = 2
  a_2 = 12
  a_3 = 112
  a_4 = 2112
  a_5 = 22112
  a_6 = 122112
  a_7 = 2122112
  ...

such that a_n is an n-digit number consisting only of 1's and 2's,
such that a_n is divisible by 2^n.  You can define the sequence
recursively: if (a_n)/2^n is even, then a_{n+1} is just 2 prepended to
(stuck on the left side of) a_n; if (a_n)/2^n is odd, then a_{n+1} is
just 1 prepended to a_n.

This is easy enough to prove: If (a_n)/2^n is even, then 2^(n+1)
divides a_n, and 2^(n+1) divides 2*10^n, and therefore 2^(n+1) divides
a_n + 2*10^n.  Similarly, if (a_n)/2^n is odd, then (10^n)/2^n = 5^n
is also odd, so (a_n + 10^n)/2^n is even, which means that a_n + 10^n
is divisible by 2^(n+1).

And that does it!

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/25/2008 at 20:44:39
From: Off
Subject: Thank you (Any power of 2 can be multiplied with result
digits 1 2 only)

Thank you Dr. Vogler for your help!  I have spent about a month and
could not crack it and you did it in a day.  Amazing...