Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature
From: Roger Stafford on 23 May 2010 20:19
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <ht9dj3$2h3$1(a)fred.mathworks.com>...
> "Bill Sinclair" <billsincl(a)aol.com> wrote in message <ht92vp$j12$1(a)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
From: Bill Sinclair on 24 May 2010 10:40
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <htcglo$65n$1(a)fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <ht9dj3$2h3$1(a)fred.mathworks.com>...
> > "Bill Sinclair" <billsincl(a)aol.com> wrote in message <ht92vp$j12$1(a)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

Hi Roger;

Thanks for getting back to me -

Yes, you nailed it on the head. I just didn't know the right math lingo for a formal description. By "cyclic" I mean an "end-around shift" or "circular shift" as in the electrical engineering concept.

I used the brute force method to get F(N) for all n <= 26, and tried factoring the numbers. They're all even numbers, except for N=2.

But still I can't come up with a formula for F(N). I am wondering if this problem has ever been solved(?)

Yours; Bill
From: Roger Stafford on 24 May 2010 18:45
"Bill Sinclair" <billsincl(a)aol.com> wrote in message <hte34u$hnf$1(a)fred.mathworks.com>...
> ........
> But still I can't come up with a formula for F(N). I am wondering if this problem has ever been solved(?)
> ........

I suspect that first matlab code I sent you (not the brute force part) will come as close as you are ever going to get to a "formula" for what you call F(N). I'll show you what I mean.

If N is a prime number p, then it is always true that

F(p) = (2^p+(p-1)*2)/p

which seems like a nice tidy little formula. However it does not extend to non-primes. If N is the product of two distinct prime numbers p and q, then the rule changes and we suddenly get a different formula

F(p*q) = (2^(p*q)+(p-1)*2^q+(q-1)*2^p+(p-1)*(q-1)*2)/(p*q)

in place of the previous one, or if N is the square of a prime number p, then you have

F(p^2) = (2^(p^2)+(p-1)*2^p+p*(p-1)*2)/p^2

again an abrupt change.

Life becomes increasingly burdensome when N is the product of three distinct primes, p, q, and r. It has the following unpleasant look:

F(p*q*r) = (2^(p*q*r)+(p-1)*2^(q*r)+(q-1)*2^(r*p)+(r-1)*2^(p*q) ...
+(q-1)*(r-1)*2^p+(r-1)*(p-1)*2^q+(p-1)*(q-1)*2^r ...
+(p-1)*(q-1)*(r-1)*2)/(p*q*r)

(Check it out with N = 2*3*5 = 30 and compare with the matlab code.)

As you can well guess, as the complexity of the factorization of N into prime factors becomes more complex, so does the formula for F(N).

Fortunately, that very simple algorithm I showed in the first section of code encompasses all of the above varieties of formulae and gives what I claim is about the closest you will ever come to a single formula for F(N). There are many mathematicians who deal primarily in prime number theory, and they would no doubt be very happy regarding such an algorithm as having "solved the problem".

Of course there is nothing unique about using matlab here. The same algorithm could be expressed in a great many computer languages, but it is difficult to express with ordinary mathematical symbols, because it is so closely tied up with the prime factorization of N.

By the way, I should warn you that that first matlab code section will work only up to N = 53. Beyond that, matlab's double precision numbers are incapable of handling the resulting large integers in an exact fashion, since their significands possess only 53 bits. The brute force code of course will run you out of time and memory long before 53.

Roger Stafford
From: Bill Sinclair on 26 May 2010 11:37
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <htevhh$ka0$1(a)fred.mathworks.com>...
> "Bill Sinclair" <billsincl(a)aol.com> wrote in message <hte34u$hnf$1(a)fred.mathworks.com>...
> > ........
> > But still I can't come up with a formula for F(N). I am wondering if this problem has ever been solved(?)
> > ........
>
> I suspect that first matlab code I sent you (not the brute force part) will come as close as you are ever going to get to a "formula" for what you call F(N). I'll show you what I mean.
>
> If N is a prime number p, then it is always true that
>
> F(p) = (2^p+(p-1)*2)/p
>
> which seems like a nice tidy little formula. However it does not extend to non-primes. If N is the product of two distinct prime numbers p and q, then the rule changes and we suddenly get a different formula
>
> F(p*q) = (2^(p*q)+(p-1)*2^q+(q-1)*2^p+(p-1)*(q-1)*2)/(p*q)
>
> in place of the previous one, or if N is the square of a prime number p, then you have
>
> F(p^2) = (2^(p^2)+(p-1)*2^p+p*(p-1)*2)/p^2
>
> again an abrupt change.
>
> Life becomes increasingly burdensome when N is the product of three distinct primes, p, q, and r. It has the following unpleasant look:
>
> F(p*q*r) = (2^(p*q*r)+(p-1)*2^(q*r)+(q-1)*2^(r*p)+(r-1)*2^(p*q) ...
> +(q-1)*(r-1)*2^p+(r-1)*(p-1)*2^q+(p-1)*(q-1)*2^r ...
> +(p-1)*(q-1)*(r-1)*2)/(p*q*r)
>
> (Check it out with N = 2*3*5 = 30 and compare with the matlab code.)
>
> As you can well guess, as the complexity of the factorization of N into prime factors becomes more complex, so does the formula for F(N).
>
> Fortunately, that very simple algorithm I showed in the first section of code encompasses all of the above varieties of formulae and gives what I claim is about the closest you will ever come to a single formula for F(N). There are many mathematicians who deal primarily in prime number theory, and they would no doubt be very happy regarding such an algorithm as having "solved the problem".
>
> Of course there is nothing unique about using matlab here. The same algorithm could be expressed in a great many computer languages, but it is difficult to express with ordinary mathematical symbols, because it is so closely tied up with the prime factorization of N.
>
> By the way, I should warn you that that first matlab code section will work only up to N = 53. Beyond that, matlab's double precision numbers are incapable of handling the resulting large integers in an exact fashion, since their significands possess only 53 bits. The brute force code of course will run you out of time and memory long before 53.
>
> Roger Stafford


Very good work Roger ! !

I assume you derived those formulas yourself.
When I get home I can check those up to N=26.
Actually, I have a good way to get above N=53, since my Fortran 2003 allows 8 byte integers, up to about 9.22E18 or 2^63 - 1. Actually, does your Matlab allow long integers like that?

But checking those results might be pretty hopeless, unless I use your recursion formula. N=26 takes a couple of minutes, and it about doubles for each new N.

Yours; Bill S.
PS: Wonder if you can get the Fields medal?
From: us on 26 May 2010 12:00
"Bill Sinclair"
> Actually, I have a good way to get above N=53, since my Fortran 2003 allows 8 byte integers, up to about 9.22E18 or 2^63 - 1. Actually, does your Matlab allow long integers like that?

a hint:

help uint64;
% and
intmax('uint64')
% ans = 18446744073709551615

us
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature