From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Discrete math question
Date: Mon, 24 May 2010 00:19:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 48
Message-ID: <htcglo$65n$>
References: <ht92vp$j12$> <ht9dj3$2h3$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1274660344 6327 (24 May 2010 00:19:04 GMT)
NNTP-Posting-Date: Mon, 24 May 2010 00:19:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:638571

"Roger Stafford" <> wrote in message <ht9dj3$2h3$>...
> "Bill Sinclair" <> wrote in message <ht92vp$j12$>...
> > Math question:
> > 
> > Given 2^n possible arrangements of N 0s and 1s,
> > how many of those are unique under cyclic permutations?
> > 
> > For example, with N=3, we have (111,000,100,110), so the answer is 4.
> > 
> > I'm not sure such a formula has ever been discovered. It certainly is NOT a trivial one.
>   There are several definitions floating around of "cyclic permutations".  The only one I can think of that makes your posed problem non-trivial is one for which the word 'unique' is not quite the right word.  Are you asking for the number of equivalence classes in the 2^n binary numbers in which two numbers are considered equivalent if and only if one can be changed to the other by a cyclic rotation of its binary digits, as for example, 1001 -> 1100 -> 0110 -> 0011?  In that case there are indeed four such equivalence classes for n = 3.  For n = 6 there are fourteen.  Is that what you are asking?
> Roger Stafford

  Using the assumption I made earlier that you are asking for the number of equivalence classes of n-bit binary numbers where cyclically rotated binaries are to be considered equivalent, below you will find two algorithms for determining this number.  Neither can be considered a "formula" in the strictest sense of the word, but the first method might be regarded as an iterative formula for finding the number, something rather more complicated than finding, say, a factorial.  The second method is a pure brute force counting method but which acts as a check on the validity of the first method.  The latter takes much longer and requires much more memory.
. . . . . . 
n = 12; % <-- Choose the number of bits

% The complicated iteration "formula"
t = n./(n:-1:1)';
d = t(round(t)==t); % List all the divisors of n
c = 2*ones(size(d)); % Start with c(1) = 2
for k = 2:size(d,1)
 t = d(k)./d((1:k-1)');
 t = find(round(t)==t); % Select all d's that are divisors of d(k)
 c(k) = 2^d(k)-sum(c(t)); % The sum of c's up to k must be 2^d(k)
N1 = sum(c./d); % Get sum of equivalence classes of each type

% The brute force method
b = (0:2^n-1)'; % List all n-bit binaries
for k = 1:2^n
 t = b(k);
 if t >= 0
  s = 2*t-(2^n-1)*(t>=2^(n-1)); % Start with s as t shifted left one
  while s ~= t
   b(s+1) = -1; % Discard equivalent binary numbers
   s = 2*s-(2^n-1)*(s>=2^(n-1)); % Do cyclic left shift of one on s
N2 = sum(b>=0); % Count total number of surviving binaries

. . . . . . 
Roger Stafford