The original message from Deja-News follows:

Subject:      Repeating Code Possibilities
From:         Shlomi Fish <shlomi@medusa.cortext.co.il>
Date:         1996/06/10
Message-ID:   <31BC1616.34C6@medusa.cortext.co.il>
Newsgroups:   rec.puzzles
[More Headers]


I've got a question in combinatorics. Let's suppose that there is a 
transmitor that trasmits a code repeatedly. Once it reaches the end of 
the code it immidiately starts broadcasting it again. For example, if 
the code is 1101 then it will broadast:

11011101110111011101....

There is no way to determine where the code starts, therefore some codes 
with the same length are equivalent. E.g., 1011 or 1110 are considered 
identical to 1101.

Keeping that in mind: suppose the code can have n different symbols or 
digits and is of length l, what is the number of different codes 
possible?

	Shlomi Fish

Eventually, I had an idea. Like I said, some codes have an effective repetition that is some integer division of the given code-length. Normal codes have l permutations. For example the code '1100' can also be written as '0110', '0011' and '1001'. However, codes of one of l's dividers have less permutations. '1010' only has two permutations: '1010' and '0101'.

Subject:      Repeating Code Riddle (+ Spoiler)
From:         ffish@euronet.co.il (Shlomi Fish)
Date:         1996/08/16
Message-ID:   <4v1nm5$583@shelly.inter.net.il>
Newsgroups:   rec.puzzles
[More Headers]


I posted this puzzle here some time ago because I didn't know the
answer. Yet, I managed to figure it out by myself after all so here's
the spoiler. First, here's the puzzle again:

Let's suppose a transmitter broadcasts a digital code over and over
without a pause between the end of the code to the beginning of the
next. Therefore, if the code is 0100 then it will broadcast:
0100010001000100010001000100010001000100...

Since there is now way to determine where the code begins 0100 is
equivalent to 1000, 0010 & 0001. Now, let's suppose we broadcast a
code of length n using b digits, how many different codes can be
broadcasted using this method?

     Shlomi Fish

(The spoiler is found below)




















































SPOILER:

In this solution I'll focus on the sub-case in which the code is
binary. I'll later replace all the relevant 2's for b's.

The basis for this solution is the fact that if a sequence has a
repeating frequency of n then it may have a smaller repeating
frequency of m only if n is equally divisible by m. (m may be equal to
1).

Now, the easiest case is the case for prime numbers. A prime number is
only divisible by 1 therefore the only possible codes with a lesser
frequency are 111111... and 00000... . That leaves 2^n-2
position-sensitive permutations. Every code has n such permutations
which gives us (2^n-2)/n such codes. 

Therefore the total number of codes for a prime number is:
       2 + (2^n - 2) / n.

The expression 2^n - 2 will prove very useful later on so let's define

T(n) = 2^n - 2.

Now let's suppose there is a number n = p*q where p, q are primes.
This number will inherit 2 codes from 1 (11111.... and 0000....),
T(p)/p codes from p, and T(q)/q codes from q. Therefore the original
permutations are 
2^(p*q) - 2 - T(p) - T(q) = T(pq) - ( T(p)+T(q) )
All in all it has:
        2 + T(p)/p + T(q)/q + [ T(pq) - (T(p)+T(q)) ] / (pq)
different codes.

Here's another simple example n = p^2 where p is a prime. This number
will inherit 2 codes from 1, and T(p)/p codes from p. Therefore it
will have:
        2 + T(p)/p + [ T(p^2) - T(p) ] / (p^2)

By now a pattern seems to be emerging so here's the solution. Given a
certain number n then q1, q2, q3....qt will symbolize the numbers
which equally divide it (excluding 1 and n). Now, let's define O(n)
as:

       O(n) = [ T(n) - (T(q1) + T(q2) + T(q3) ... + T(qt) ) ] / n
       ( O(1) = 2)

O(n) denotes the number of codes which are "original" to n and weren't
inherited from any smaller number.

Now if q1, q2...qt will again stand for the dividers of n then the
total number of codes n have are:

       A(n) = O(1) + O(q1) + O(q2) + O(q3) + .. + O(qt) + O(n)


      Shlomi Fish

Back to Shlomi Fish' Homepage