Discrete math question
Bill Sinclair
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.
Walter Roberson
N+1 of them are unique -- 0 bits set, 1 bit set, 2 bits set ... N bits
set. The rest are reorderings of these.
Roger Stafford
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
Walter Roberson
> "Bill Sinclair" <bill...@aol.com> wrote in message
> <ht92vp$j12$1...@fred.mathworks.com>...
>> Given 2^n possible arrangements of N 0s and 1s,
>> how many of those are unique under cyclic permutations?
> 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.
Sounds like your cyclic rotations are pairwise, Roger. If you were to
use the more general definition of "cyclic permutations" that allows for
arbitrary permutations, then because any bit string can be permuted
directly into any other bit string of the same length and same number of
bits set, the only difference between the possibilities would be the
number of bits set.
Roger Stafford
> Sounds like your cyclic rotations are pairwise, Roger. If you were to
> use the more general definition of "cyclic permutations" that allows for
> arbitrary permutations, then because any bit string can be permuted
> directly into any other bit string of the same length and same number of
> bits set, the only difference between the possibilities would be the
> number of bits set.
They aren't *my* cyclic permutations, Walter. I am aware of the several standard definitions. What I suggested was the only way I could make sense out of the request. Can you think of another way that is consistent with Bill's example and that is non-trivial? Anyway, let's wait and see what he has to say about it.
Roger Stafford
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
Bill Sinclair
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
Roger Stafford
> ........
> 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
Bill Sinclair
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?
us
> 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
Alan B
If you can compute the first few terms by brute force, this website is useful:
http://www.research.att.com/~njas/sequences/index.html?q=2%2C3%2C4%2C6%2C8%2C14&language=english&go=Search
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?
Thanks for the suggestion, Alan.
Bill, your problem is known as the "necklace" problem, namely the number of unique fixed necklaces of length n which can be made out of b (= 2 in your case) kinds of beads. The formula is:
a(n) = (1/n)*Sum_{ d divides n } phi(d)*b^(n/d),
where phi is the Euler phi totient function defined as phi(d) = the number of positive integers less than d and relatively prime to d. This is written up in the Wolfram site at:
http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/31/08/ShowAll.html
I ran the iteration code I sent you for n up to 53. The numbers agreed as far as the sequence went (35 of them) in the "sequence" site Alan referred to. Hence, no Fields medal for anybody.
In answer to your question, yes I did derive that method myself, being naively unaware at the time of others' work on this. The theory is not difficult. Binary numbers of n digits can be classified in accordance with the least number of cyclic shifts before they repeat. Such a number of shifts must necessarily be a divisor of n. In the matlab code I called the total number in each k-th category c(k) and that corresponding least number of cyclic shifts d(k). Clearly the sum of all the c(k)'s must be 2^n. Note however that in each category k, the situation is equivalent to the question of binary numbers with only d(k) digits. Therefore the sum of that c(k) and all preceding c's whose corresponding d is a divisor of d(k), must be 2^d(k). Hence a recursion can be performed starting at one digit and going through all the divisors of n until finally evaluating c(n). Then the total
number of unique numbers can be found by dividing each c(k) by d(k) and finding the sum of these.
Roger Stafford
Bill Sinclair
Hi Roger;
Really neat stuff !
Anyway, I'm wondering - given the formula for F(p), p any prime.
How would you prove the result is always an integer? That is if you don't
know ahead of time where it was derived from.
2^p is never divisible by P unless P=2, and 2*(p-1) "probably" isn't either.
But somehow magically, when you combine them you get a number which is divisible
by p. Seems mysterious to me anyway.....
Yours; Bill
Roger Stafford
> Hi Roger;
>
> Really neat stuff !
>
> Anyway, I'm wondering - given the formula for F(p), p any prime.
> How would you prove the result is always an integer? That is if you don't
> know ahead of time where it was derived from.
>
> 2^p is never divisible by P unless P=2, and 2*(p-1) "probably" isn't either.
> But somehow magically, when you combine them you get a number which is divisible
> by p. Seems mysterious to me anyway.....
>
> Yours; Bill
If p is prime, then the fact that (2^p+(p-1)*2)/p is always an integer is equivalent to what is known as Fermat's Little Theorem (to distinguish it from the famous Fermat's Last Theorem.) The little theorem states that if p is a prime number, then a^p-a is divisible by p for any integer a.
If we let a = 2 and p be a prime number, then
F(p) = ((2^p+(p-1)*2)/p = (2^p-2)/p + 2
which would therefore be an integer since it is 2 greater than the integer quotient promised by the little theorem.
You can find proofs of the little theorem at
http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem
You will be intrigued by the fact that here they do one proof using "necklaces" which comes right back to cyclic shifts of binary numbers.
Roger Stafford
Bill Sinclair
Thanks very much Roger -
I printed out the article. Actually, I should have seen the similarity right away between the "little theorem" and the necklace formula.
Just curious: Has anyone ever proven Goldbach's conjecture and/or the "twin primes" conjecture? One could generalize the twin primes conjecture by stating "any arbitrary pattern of prime spacing is repeated infinitely many times." For example, primes separated by 4,6,8, etc. Of course a spacing of ONE only happens once.......
Roger Stafford
> Just curious: Has anyone ever proven Goldbach's conjecture and/or the "twin primes" conjecture? .......
Not as far as I know. The two Wikipedia articles below are concerned with just that:
http://en.wikipedia.org/wiki/Goldbach's_conjecture
http://en.wikipedia.org/wiki/Twin_prime
Roger Stafford