Finding Integer Pairs Whose Product Consists Only of 1's and 0'sDate: 10/06/2004 at 20:21:23 From: Kris Subject: How can the product of 2 numbers contain only ones and zeros Given the base-10 representation of any integer a, does there exist a non-zero integer b such that the base-10 representation of the product ab contains only ones and zeros? One example (most obvious) is a = 5 and b = 2 ... ab = 5 x 2 = 10. Another is a = 17 and b = 653 ... ab = 17 x 653 = 11101. How can you come up with two numbers such that the product only contains ones and zeros? I can guess and figure out a few, but there must be an easier way, or some sort of pattern. Date: 10/07/2004 at 03:52:29 From: Doctor Jacques Subject: Re: How can the product of 2 numbers contain only ones and zeros Hi Kris, Let us call a number "good" if it statisfies the required property, i.e., if there is a number b such that the product a*b contains only the digits 0 and 1 when represented in base 10. We want to show that all numbers are "good". We will first examine a few easy cases. * 0 and 1 are good This is obvious. * If a is good, then 2a is good. Indeed, if a*b = N, then (2a)(5b) = 10*N, and this is just N with an additional 0 on the right--if N contains only 0's and 1's, then so does 10*N. * If a is good, then 5a is good. The proof is exactly the same--simply interchange 2 and 5. * If a is good, then 3a is good. This is a little trickier. Assume that we have: a*b = N where N consists only of 0's and 1's. Assume that N contains k digits. Consider the number: c = 1O^(2k) + 10^k + 1 This number contains only three 1's (at positions 0, k, and 2k). By the divisibility rules for 3, c is a multiple of 3, and we can write c = 3d. We have therefore a*(b*c) = a*(3*b*d) = (3a)*(b*d)= c*N Now, c*N is simply N repeated 3 times. If N only contains 1's and 0's, then so does c*N, and this shows that (3a) is "good". The conclusion of all this is that we may assume that a >= 2 and a is not divisible by 2, 3, or 5. If a is not divisible by 2 or 5, the decimal expansion of 1/a is purely periodic, and, if k is the length of the period, then (10^k - 1) is divisible by a; in fact, k is the smallest integer such that: 10^k = 1 (mod a) (If you are not famliliar with this, see, for example: Shortcut: Repeating Decimals to Equivalent Fractions http://mathforum.org/library/drmath/view/58176.html or many other pages you can find in our archive: Search Dr. Math http://mathforum.org/library/drmath/mathgrepform.html by searching for "repeating decimal".) Of course, any number of the form 10^k - 1 consists only of 9's, and is divisible by 9. We can write: 10^k - 1 = 9*N where N is a sequence of 1's. As a divides 10^k - 1, there is a "b" such that: a*b = 10^k - 1 = 9*N As this number is a multiple of 9, and we assumed that a was not a multiple of 3, b must be a multiple of 9, say b = 9c. We have then: a*(9c) = 9N a*c = N and N contains only 1's - "a" is a good number. To see how it works on an example, let us consider a = 246 = 2*3*41. We begin by removing all factors 2, 3, and 5, leaving 41. The decimal expansion of 1/41 is; 1/41 = 0.02439... and the period has length 5, which shows that 41 divides 10^5 - 1. Indeed, we have: 10^5 - 1 = 99999 = 41*2439 = 41*9*271 and, dividing by 9, we have: 41*271 = 11111 Note that the number on the right is not a multiple of 3, but a = 246 is a multiple of 3. We use the technique explained above, i.e., we repeat the number 3 times: 41*2710027100271 = 111111111111111 (Note that we had to extend the number 271 to 5 digits to match the length of the number on the right.) The factor of 41 is a multiple of 3 (by construction), in fact, we have: 2710027100271 = 3 * 903342366757 and this allows us to write: (3*41)*903342366757 = 111111111111111 This already shows that 41*3 = 123 is a good number. To get to 246, we must introduce a factor of 2, and we do this by multiplying by 2 and 5 on both sides: (2*3*41)*(5*903342366757) = 1111111111111110 246 * 4516711833785 = 1111111111111110 which shows that 246 is a good number. Note that, although this technique proves that all numbers are good, and does, in fact, give an explicit method for finding a suitable factor "b", it will not, in general, give the smallest possible such factor. In fact, the factor produced by this method is such that all the 1's in the product are consecutive, with all the 0's at the end. For example, we have: 337*3 = 1011 but, if we start with the number 337, and apply the previous method, we will get a very large factor, since the decimal expansion of 337 has period length 336; the product on the right will consist of 336 "1" digits. I do not know any method that could allow you to find the smallest possible factor "b" (except, of course, by listing all the multiples of a...). Note also that a similar argument is valid for any base; in that case, you have to replace the special factors 2, 3, and 5 by the prime factors of b and b-1, if b is the base. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/