Integer N formed with digits 1 and 2 only and divisibility by 2^n

Let   N   be a n-digit number that contains only the digits   1   and   2.

 

If   n = 2,   that is, a 2-digit number that contains both the digits 1 and 2.
The set of these numbers is   (12, 21)

Only   12   is divisible by   2^2.

12 mod 2^2   =   0
21 mod 2^2   =   1

If   n = 3.   The set is   (112, 121, 211, 221, 212, 122)

112   =   2 * 2 * 2 * 2 * 7
121   =   11 * 11
211   is a prime number.
221   =   13 * 17
212   =   2 * 2 * 53
122   =   2 * 61

Only   112   is divisible by   2^3

122 mod 2^3 = 2
121 mod 2^3 = 1
112 mod 2^3 = 0

211 mod 2^3 = 3
221 mod 2^3 = 5
212 mod 2^3 = 4

 

If   n = 4.   The set is  
(1112, 1121, 1211, 2111, 2211, 2121, 2112, 1212, 1122, 2221, 2212, 2122, 1222, 1221)

1112   =   2 * 2 * 2 * 139
1121   =   19 * 59
1211   =   7 * 173
2111   is a prime number.
2211   =   3 * 11 * 67
2121   =   3 * 7 * 101
2112   =   2 * 2 * 2 * 2 * 2 * 2 * 3 * 11
1212   =   2 * 2 * 3 * 101
1122   =   2 * 3 * 11 * 17
2221   is a prime number.
2212   =   2 * 2 * 7 * 79
2122   =   2 * 1061
1222   =   2 * 13 * 47
1221   =   3 * 11 * 37

Only   2112   is divisible by   2^4

1112 mod 2^4 = 8
1121 mod 2^4 = 1
1211 mod 2^4 = 11
1212 mod 2^4 = 12
1221 mod 2^4 = 5
1122 mod 2^4 = 2
1222 mod 2^4 = 6

2111 mod 2^4 = 15
2211 mod 2^4 = 3
2121 mod 2^4 = 9
2112 mod 2^4 = 0
2221 mod 2^4 = 13
2212 mod 2^4 = 4
2122 mod 2^4 = 10
 

These examples show that for   n = 2,   3   and   4   there is a unique number that is divisible by   2^n

Generalize this.
That is, prove that for any integer   N   that contain both the digits   1   and   2,   there exists only one n-digit number that is divisible by   2^n.

Check out   A126933,   A053312

We can always find an n-digit number that is formed with only digits 1 and 2 and divisible by 2^n.

It remains to prove that there exists a unique n-digit number.

To prove that   N mod 2^n = 0   is unique.

 
 
Let   A_n   and   B_n   be   n-digit numbers.

A_n = a(1).a(2).a(3)….a(n)     and     B_n = b(1).b(2).b(3)….b(n)

where each of   a(1), a(2), …, a(n)   and   b(1), b(2), …, b(n)   is 1 or 2.

Let’s suppose that

a(1).a(2).a(3)….an   ≡   b(1).b(2.b3)….bn   (mod 2^n)

Then clearly

a(1).a(2).a(3)….an   ≡   b(1).b(2).b(3)….b(n)   (mod 2)

then we also have

a(1).a(2).a(3)….a(n)   ≡   a(n)   (mod 2)
b(1).b(2).b(3)….b(n)   ≡   b(n)   (mod 2)

so     a(n)   ≡   b(n)   (mod 2)

But     a(n) is either 1 or 2     and     b(n) either 1 or 2

so     a(n) = b(n) = 1     or     a(n) = b(n) = 2
In either case     a(n) = b(n)

Hence     a(n).a(2)…a(n-1)   ≡   b(1).b(2)….b(n-1) ( mod 2^(n-1) )

we can finish by induction to conclude     a(1).a(2)…a(n) = b(1).b(2)….b(n)
 
 
 
 

About these ads

About benvitalis

math grad - Interest: Number theory
This entry was posted in Math Beauty, Number Puzzles and tagged , . Bookmark the permalink.

One Response to Integer N formed with digits 1 and 2 only and divisibility by 2^n

  1. Do recursively: if string of 1′s & 2′s of length n is div by 2^n, prepend 1 if quotient is odd, 2 if even http://bit.ly/VGosp9

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