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

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search