|Note: I'm not sure that the solution given on this page is entirely accurate. I'll verify that point and correct this document if needed. Meanwhile, please take the information here with a grain of salt.|
The original message from Deja-News follows:
Subject: Repeating Code Possibilities From: Shlomi Fish <firstname.lastname@example.org> 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 FishA final note about this problem: if a code has an effective repetition that is some integer division of l, it's still of length l. E.g: the code 10101010... is still considered the 4-bits code 1010 (or 0101). The continuation which includes the answer can be found a couple of pages below.
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: email@example.com (Shlomi Fish) Date: 1996/08/16 Message-ID: <firstname.lastname@example.org> 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