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

<!-- X-URL: http://x10.dejanews.com/getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1 -->
<BASE HREF="http://x10.dejanews.com/getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1">

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

</HEAD>
<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="http://web3.dejanews.com/"><img src="http://web3.dejanews.com/gifs/dnlogo_r7.gif" align=middle alt="Deja News" height=70 width=103 border=0></a></td>
<td height=70 width=367 nowrap><img src="http://web3.dejanews.com/gifs/1x1.gif" align=bottom alt="" height=22 width=1 border=0><a href="http://web3.dejanews.com/"><b>Home</b></a>&nbsp;&#183;
<a href="http://gp.dejanews.com/gtplacer?site=dn&location=link.home.infospace&cid=882122744.1147601385"><b>Online Resources</b></a><br>
<img src="http://web3.dejanews.com/gifs/redline.gif" alt="-------------------------------------" height=2 width=367 vspace=2 border=0><br>
<font size=1><a href="http://web3.dejanews.com/home_qs.shtml">Quick Search</a>&nbsp;&#183;
<a href="http://web3.dejanews.com/home_ps.shtml">Power Search</a>&nbsp;&#183;
<a href="http://web3.dejanews.com/home_sf.shtml">Search Filter</a>&nbsp;&#183;
<a href="http://web3.dejanews.com/home_if.shtml">Interest Finder</a>&nbsp;&#183;
<a href="http://web3.dejanews.com/home_bg.shtml">Browse Groups</a></font>
<br>
<font size=5>&nbsp;</font><a href="http://gp.dejanews.com/gtplacer?site=dn&location=link.dynamic.ibm&cid=882122744.1147601385"><font color=c60012>IBM Netfinity...just better business</font></a></td></tr>
<tr><td colspan=2><hr noshade size=1></td></tr>
</table>

<table cellspacing=0 cellpadding=0 width=470 border=0><tr><td>
<A HREF="http://gp1.dejanews.com/gtc?id=8720&tm=882122745.241903&site=dn&location=rec.puzzles&keywords=%2a&cr=%7c%7c%7c%7c%7c%7c%7c%7c">
<IMG ALIGN=MIDDLE HEIGHT=60 WIDTH=468 SRC="http://web2.dejanews.com/ads/44/1122694344-8759.gif" ALT="Search the Yellow Pages" border=1></A></td></tr><tr align=center><td><font size=-1><A HREF="http://gp1.dejanews.com/gtc?id=8720&tm=882122745.241903&site=dn&location=rec.puzzles&keywords=%2a&cr=%7c%7c%7c%7c%7c%7c%7c%7c">
Find Phone Numbers and E-Mail Addresses Anywhere!!</a></font></td></tr>
</table><br>
<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="http://web3.dejanews.com/gifs/text.gif" align=absmiddle width=22 height=20 border=0 alt=""></a>&nbsp;&nbsp;&nbsp;<a href="http://web3.dejanews.com/help/help_art.shtml">Help<img src="http://web3.dejanews.com/gifs/qm.gif" 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="http://x10.dejanews.com/getdoc.xp?recnum=7783539&server=db97p5x&CONTEXT=882122683.1218314336&hitnum=0"><IMG ALT="[Previous Article]" BORDER=0 SRC="http://web3.dejanews.com/gifs/prev.gif" width=31 height=25 hspace=6><br><font size=-1>Previous<br>Article</font></A></td>
<td><A HREF="http://x10.dejanews.com/getdoc.xp?recnum=9104260&server=db96q2&CONTEXT=882122683.1218314336&hitnum=2"><IMG ALT="[Next Article]" BORDER=0 SRC="http://web3.dejanews.com/gifs/next.gif" width=32 height=25 hspace=6><br><font size=-1>Next<br>Article</font></A></td>
<td><A HREF="http://x10.dejanews.com/dnquery.xp?search=next&ST=PS&site=dn&offsets=&svcclass=dnserver&CONTEXT=882122683.1218314336"><IMG ALT="[Current Results]" BORDER=0 SRC="http://web3.dejanews.com/gifs/curr.gif" width=26 height=27 hspace=6><br><font size=-1>Current<br>Results</font></A></td>
<td><A HREF="http://x10.dejanews.com/dnquery.xp?search=thread&filter=%7bdb97p5x%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d%20%7bdb96q2%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d%20%7bdb96q3%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d&svcclass=dnserver&threaded=1&ST=PS&CONTEXT=882122683.1218314336&HIT_CONTEXT=882122683.1218314336&HIT_NUM=1&recnum=%3c4v1nm5$583@shelly.inter.net.il%3e%231/1"><IMG ALT="[View Thread]" BORDER=0 SRC="http://web3.dejanews.com/gifs/thr.gif" width=34 height=27 hspace=6><br><font size=-1>View<br>Thread</font></A></td>
<td><A HREF="/profile.xp?author=ffish@euronet.co.il%20(Shlomi%20Fish)&ST=PS"><IMG ALT="[Author Profile]" BORDER=0 SRC="http://web3.dejanews.com/gifs/auth.gif" width=25 height=28 hspace=6><br><font size=-1>Author<br>Profile</font></A></td>
<td><A HREF="http://postnews.dejanews.com/post.xp?NG=rec.puzzles"><IMG ALT="[Post Message]" BORDER=0 WIDTH=31 HEIGHT=28 hspace=6 SRC="http://web3.dejanews.com/gifs/post_a.gif"><br><font size=-1>Post<br>Message</font></A></td>
</tr></table><br><PRE>
<B>Subject:      <FONT SIZE=+1 color="#c60012">Repeating Code Riddle (+ Spoiler)</FONT>
From:         ffish@euronet.co.il (Shlomi Fish)
Date:         1996/08/16
Message-ID:   &lt;4v1nm5$583@shelly.inter.net.il&gt;
Newsgroups:   rec.puzzles
<A HREF="http://x10.dejanews.com/getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1&AH=1">[More Headers]</A>
</B>

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 &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)




















































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 &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
</PRE>


<hr width=470 align=left><br><table cellspacing=0 cellpadding=0 width=470 border=0><tr><td>
<A HREF="http://gp1.dejanews.com/gtc?id=8720&tm=882122745.241903&site=dn&location=rec.puzzles&keywords=%2a&cr=%7c%7c%7c%7c%7c%7c%7c%7c">
<IMG ALIGN=MIDDLE HEIGHT=60 WIDTH=468 SRC="http://web2.dejanews.com/ads/44/1122694344-8759.gif" ALT="Search the Yellow Pages" border=1></A></td></tr><tr align=center><td><font size=-1><A HREF="http://gp1.dejanews.com/gtc?id=8720&tm=882122745.241903&site=dn&location=rec.puzzles&keywords=%2a&cr=%7c%7c%7c%7c%7c%7c%7c%7c">
Find Phone Numbers and E-Mail Addresses Anywhere!!</a></font></td></tr>
</table>
<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="http://x10.dejanews.com/getdoc.xp?recnum=7783539&server=db97p5x&CONTEXT=882122683.1218314336&hitnum=0">Previous</A> &nbsp;|&nbsp;
<A HREF="http://x10.dejanews.com/getdoc.xp?recnum=9104260&server=db96q2&CONTEXT=882122683.1218314336&hitnum=2">Next</A> &nbsp;|&nbsp;
<A HREF="http://x10.dejanews.com/dnquery.xp?search=next&ST=PS&site=dn&offsets=&svcclass=dnserver&CONTEXT=882122683.1218314336">Results</A> &nbsp;|&nbsp;
<A HREF="http://x10.dejanews.com/dnquery.xp?search=thread&filter=%7bdb97p5x%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d%20%7bdb96q2%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d%20%7bdb96q3%20%7b%7b%7eg%20rec.puzzles%01%7ea%20Fish%7d%7d%7d&svcclass=dnserver&threaded=1&ST=PS&CONTEXT=882122683.1218314336&HIT_CONTEXT=882122683.1218314336&HIT_NUM=1&recnum=%3c4v1nm5$583@shelly.inter.net.il%3e%231/1">View Thread</A> &nbsp;|&nbsp;
<A HREF="/profile.xp?author=ffish@euronet.co.il%20(Shlomi%20Fish)&ST=PS">Author Profile</A> &nbsp;|&nbsp;
<A HREF="http://postnews.dejanews.com/post.xp?NG=rec.puzzles">Post Message</A> &nbsp;|&nbsp;
<A HREF="http://web3.dejanews.com/errors/old_followup.shtml">Post Reply</A> &nbsp;|&nbsp;
<A HREF="mailto:ffish@euronet.co.il">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="http://web3.dejanews.com/info/policy.shtml">Deja News, Inc.</A> All rights reserved.</font>
</td></tr>
</table>

</td></tr></table>
</body>
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 ProjectModifiedEvent.java.
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.