-<TITLE>Math-Ventures: On and on it seems to go...</TITLE>

+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"

+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

+<html xmlns="http://www.w3.org/1999/xhtml">

+content="HTML Tidy for Linux/x86 (vers 1st August 2002), see www.w3.org" />

+<title>Math-Ventures: On and on it seems to go...</title>

+<body bgcolor="#FFFFFF">

+<h2>On and on it seems to go...</h2>

-<BODY BGCOLOR="#FFFFFF">

+A while ago, I was introduced to a couple of questions about

+digital codes being broadcasted. This made me think of a new code

+problem. I thought about it a bit, and saw that I couldn't figure

+out the answer. So, I decided to post it to the Usenet newsgroup

+rec.puzzles which is dedicated to riddles and puzzles of all sorts.

+<p>The original message from Deja-News follows:</p>

-<CENTER><H2>On and on it seems to go...</H2></CENTER>

-A while ago, I was introduced to a couple of questions about digital codes

-being broadcasted. This made me think of a new code problem. I thought about it a

-bit, and saw that I couldn't figure out the answer. So, I decided to post it

-to the Usenet newsgroup rec.puzzles which is dedicated to riddles and

-puzzles of all sorts.<P>

-The original message from Deja-News follows:<P>

-<B>Subject: <FONT SIZE=+1 color="#c60012">Repeating Code Possibilities</FONT>

+<b>Subject: <font size="+1"

+color="#C60012">Repeating Code Possibilities</font>

From: Shlomi Fish <shlomi@medusa.cortext.co.il>

Message-ID: <31BC1616.34C6@medusa.cortext.co.il>

-<A HREF="http://x10.dejanews.com/getdoc.xp?recnum=9104260&server=db96q2&CONTEXT=882122683.1218314336&hitnum=2&AH=1">[More Headers]</A>

+href="http://x10.dejanews.com/getdoc.xp?recnum=9104260&server=db96q2&CONTEXT=882122683.1218314336&hitnum=2&AH=1">[More Headers]</a>

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

digits and is of length l, what is the number of different codes

-A 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).

+A 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. <br />

+ Well, the rec.puzzles guys did not know how to solve it either,

+and someone suggested that I should post it to sci.math instead.

+<p>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'.</p>

-The continuation which includes the answer can be found a couple of pages

+<p>So, I posted the following message to rec.puzzles a couple of

+monthes after my original posting. The solution presented there is

+not intirely correct, so read my notes below.</p>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-<BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>

-Well, the rec.puzzles guys did not know how to solve it either, and someone

-suggested that I should post it to sci.math instead.<P>

-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'.<P>

-So, I posted the following message to rec.puzzles a couple of monthes after

-my original posting. The solution presented there is not intirely correct,

-<B>Subject: <FONT SIZE=+1 color="#c60012">Repeating Code Riddle (+ Spoiler)</FONT>

+<b>Subject: <font size="+1"

+color="#C60012">Repeating Code Riddle (+ Spoiler)</font>

From: ffish@euronet.co.il (Shlomi Fish)

Message-ID: <4v1nm5$583@shelly.inter.net.il>

-<A HREF="http://x10.dejanews.com/getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1&AH=1">[More Headers]</A>

+href="http://x10.dejanews.com/getdoc.xp?recnum=7500598&server=db96q3&CONTEXT=882122683.1218314336&hitnum=1&AH=1">[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

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

-O(n) denotes the number of codes which are ~~"~~original~~"~~ to n and weren't

+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

-Well, I didn't take in mind that a number can indirectly receive codes from

-a divider by two or more other dividers (like 12 that gets codes from 2

-through both 4 and 6). Thus, O(n) the function that denotes the number of

-"original" codes of n should be recursive and defined as following:<P>

+Well, I didn't take in mind that a number can indirectly receive

+codes from a divider by two or more other dividers (like 12 that

+gets codes from 2 through both 4 and 6). Thus, O(n) the function

+that denotes the number of "original" codes of n should be

+recursive and defined as following:

+<p><b>O(1) = 2</b><br />

+<b>O(n) = T(n)/n</b> for every prime number n<br />

+<b>O(n) = [ T(n) - (O(q1)*q1 + O(q2)*q2 + .. O(qt)*qt ) ] / n</b>

+for all other numbers<br />

-<B>O(n) = T(n)/n</B> for every prime number n <BR>

-<B>O(n) = [ T(n) - (O(q1)*q1 + O(q2)*q2 + .. O(qt)*qt ) ] / n</B> for all other

+<p>Otherwise the solution is fine. You can view a C program that

+calculates the number of such codes for all numbers up to 24 <a

+href="check_codes.c">here</a>.</p>

+<h3><a href="./">Back to the Math-Ventures Web page</a></h3>

-Otherwise the solution is fine. You can view a C program that calculates the

-number of such codes for all numbers up to 24 <A HREF="check_codes.c">here</A>.

+<h3><a href="../">Back to Shlomi Fish' Homepage</a></h3>

-<A HREF="./"><H3>Back to the Math-Ventures Web page</H3></A><P>

-<A HREF="../"><H3>Back to Shlomi Fish' Homepage</H3></A>