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