Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Exponents
Middle School Exponents
Middle School Factoring Numbers
Middle School Prime Numbers

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/