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

<!-- X-URL: -->

<HEAD><TITLE>Deja News - Article</TITLE>

<body bgcolor="#ffffff" text="#000000" link="#0000ff" vlink="#52188c" alink="#ff0000">

<table height=70 width=470 cellpadding=0 cellspacing=0 border=0>
<tr valign=top align=right>
<td height=70 width=103><a href=""><img src="" align=middle alt="Deja News" height=70 width=103 border=0></a></td>
<td height=70 width=367 nowrap><img src="" align=bottom alt="" height=22 width=1 border=0><a href=""><b>Home</b></a>&nbsp;&#183;
<a href=""><b>Online Resources</b></a><br>
<img src="" alt="-------------------------------------" height=2 width=367 vspace=2 border=0><br>
<font size=1><a href="">Quick Search</a>&nbsp;&#183;
<a href="">Power Search</a>&nbsp;&#183;
<a href="">Search Filter</a>&nbsp;&#183;
<a href="">Interest Finder</a>&nbsp;&#183;
<a href="">Browse Groups</a></font>
<font size=5>&nbsp;</font><a href=""><font color=c60012>IBM Netfinity...just better business</font></a></td></tr>
<tr><td colspan=2><hr noshade size=1></td></tr>

<table cellspacing=0 cellpadding=0 width=470 border=0><tr><td>
<A HREF="">
<IMG ALIGN=MIDDLE HEIGHT=60 WIDTH=468 SRC="" ALT="Search the Yellow Pages" border=1></A></td></tr><tr align=center><td><font size=-1><A HREF="">
Find Phone Numbers and E-Mail Addresses Anywhere!!</a></font></td></tr>
<table cellspacing=0 cellpadding=2 width=470 border=0>
<tr><td bgcolor="#cccccc"><font face="arial,helvetica" size=4><b>&nbsp;Article 2 of exactly 3</b></font></td>
<td bgcolor="#cccccc" align=right><a href="getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1&fmt=raw">Text Only<img src="" align=absmiddle width=22 height=20 border=0 alt=""></a>&nbsp;&nbsp;&nbsp;<a href="">Help<img src="" width=22 height=20 border=0 align=absmiddle alt="?"></a></td></tr>
</table><table cellspacing=0 cellpadding=2 border=0><tr align=center>
<td><A HREF=""><IMG ALT="[Previous Article]" BORDER=0 SRC="" width=31 height=25 hspace=6><br><font size=-1>Previous<br>Article</font></A></td>
<td><A HREF=""><IMG ALT="[Next Article]" BORDER=0 SRC="" width=32 height=25 hspace=6><br><font size=-1>Next<br>Article</font></A></td>
<td><A HREF=""><IMG ALT="[Current Results]" BORDER=0 SRC="" width=26 height=27 hspace=6><br><font size=-1>Current<br>Results</font></A></td>
<td><A HREF="$"><IMG ALT="[View Thread]" BORDER=0 SRC="" width=34 height=27 hspace=6><br><font size=-1>View<br>Thread</font></A></td>
<td><A HREF="/profile.xp?"><IMG ALT="[Author Profile]" BORDER=0 SRC="" width=25 height=28 hspace=6><br><font size=-1>Author<br>Profile</font></A></td>
<td><A HREF=""><IMG ALT="[Post Message]" BORDER=0 WIDTH=31 HEIGHT=28 hspace=6 SRC=""><br><font size=-1>Post<br>Message</font></A></td>
<B>Subject:      <FONT SIZE=+1 color="#c60012">Repeating Code Riddle (+ Spoiler)</FONT>
From: (Shlomi Fish)
Date:         1996/08/16
Message-ID:   &lt;4v1nm5$;
Newsgroups:   rec.puzzles
<A HREF="">[More Headers]</A>

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:

Since there is now way to determine where the code begins 0100 is
equivalent to 1000, 0010 &amp; 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)


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

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)

       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 &quot;original&quot; 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

<hr width=470 align=left><br><table cellspacing=0 cellpadding=0 width=470 border=0><tr><td>
<A HREF="">
<IMG ALIGN=MIDDLE HEIGHT=60 WIDTH=468 SRC="" ALT="Search the Yellow Pages" border=1></A></td></tr><tr align=center><td><font size=-1><A HREF="">
Find Phone Numbers and E-Mail Addresses Anywhere!!</a></font></td></tr>
<table cellspacing=0 cellpadding=0 border=0><tr valign=center>
<td><nobr><hr align=left noshade size=1 width=470>
<font size=-1 color="#666666"><A HREF="">Previous</A> &nbsp;|&nbsp;
<A HREF="">Next</A> &nbsp;|&nbsp;
<A HREF="">Results</A> &nbsp;|&nbsp;
<A HREF="$">View Thread</A> &nbsp;|&nbsp;
<A HREF="/profile.xp?">Author Profile</A> &nbsp;|&nbsp;
<A HREF="">Post Message</A> &nbsp;|&nbsp;
<A HREF="">Post Reply</A> &nbsp;|&nbsp;
<A HREF="">Send Email</A></font></nobr></td></tr></table>
<table width=470 cellpadding=0 cellspacing=0 border=0>
<tr><td align=center><hr noshade size=1 width=470>
<font size=-1>Copyright &copy; 1995-97 <A HREF="">Deja News, Inc.</A> All rights reserved.</font>

Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.