Code with Only a String of 1's
Date: 10/28/2002 at 06:58:30 From: Daniel Subject: Code with only a string of 1's You need to send a numeric code to someone, such as one used to unlock a padlock. Your only ability to convey the code is to send this person a piece of paper with a string of 1's on it. There can be no spaces on the piece of paper, no other characters/letters/numbers - just 1's. How can you convey your code? Keep in mind that codes are not necessarily one number, but can be a combination of numbers, i.e, 12 31 56 is not the same as 123156, so to represent the former, you can't just send 123156 1's on the piece of paper because the recipient will not be able to know that it really represents 12, 31, and 56. You need to figure out the way to send the code for all types of codes. I don't know how to solve it but it would be something like this: Let's say you have the code 2 3 4 ... You write this many zeros: 2*2^1+3*2^2+4*2^3 + ... = 2+12+32 = 46 But this isn't an adequate answer. Can you help me?
Date: 10/28/2002 at 16:09:20 From: Doctor Mike Subject: Re: Code with only a string of "1"s Daniel, This is an interesting problem. I think you can use the fact that a positive integer can be factored in one and only one way into a product of prime numbers, if you agree that the multiplications are written from smaller to larger. That is, 2*13*2 is considered to be the same factorization as 2*2*13. Let p1 be the smallest prime 2. Let p2 be the next smallest prime 3. Let p3, p4, p5 be 5, 7, 11. And in general let pN be the N-th prime. To code a sequence like A, B, C compute 2^A * 3^B * 5^C and send that many 1 symbols. To decode this, the receiver merely has to count the ones, factor that number, and read off the exponents of the primes. Using the above notation: p1^A * p2^B * p3^C For your example of 2,3,4 you send 2*2*3*3*3*5*5*5*5 or 67500 ones in a row. For your other sequence 12, 31, 56 send 2^12 * 3^31 * 5^56 ones in a row. These numbers get to be really big. I didn't say it was going to be easy to use this code, though. This just works for sequences of positive numbers. You can include zero into the scheme easily, using the fact that a positive integer to the zero power is one. So the sequence 1,1,0,3,2 could be sent as p1^1 * p2^1 * p3^0 * p4^3 * p5^2, which is the same as 2 * 3 * 1 * 7 * 7 * 7 * 11 * 11 ones. When the receiver factors it as 2*3*7*7*7*11*11, the absence of any 5 in the product indicates that the third number in the sequence is zero. There may be other ways, but this is the first one I thought of. - Doctor Mike, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.