# shlomi-fish-homepage / old / MathVentures / dn_rep_spoiler.html

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200``` ``` Deja News - Article
Home · Online Resources

Quick Search · Power Search · Search Filter · Interest Finder · Browse Groups

Find Phone Numbers and E-Mail Addresses Anywhere!!

Article 2 of exactly 3 Text Only   Help

Previous
Article

Next
Article

Current
Results

View

Author
Profile

Post
Message

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

Find Phone Numbers and E-Mail Addresses Anywhere!!

Previous  |  Next  |  Results  |  View Thread  |  Author Profile  |  Post Message  |  Post Reply  |  Send Email