Path: news.mathworks.com!not-for-mail
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$1@fred.mathworks.com>
References: <ht92vp$j12$1@fred.mathworks.com> <ht9dj3$2h3$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1274660344 6327 172.30.248.35 (24 May 2010 00:19:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 24 May 2010 00:19:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:638571

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ht9dj3$2h3$1@fred.mathworks.com>...
> "Bill Sinclair" <billsincl@aol.com> wrote in message <ht92vp$j12$1@fred.mathworks.com>...
> > 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.
. . . . . . 
clear
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)
end
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
  end
 end
end
N2 = sum(b>=0); % Count total number of surviving binaries

[N1;N2]
. . . . . . 
Roger Stafford