Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature
From: Alan B on 26 May 2010 12:04
"Bill Sinclair" <billsincl(a)aol.com> wrote in message <htjf70$oj3$1(a)fred.mathworks.com>...
> "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?

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
From: Roger Stafford on 26 May 2010 20:31
"Bill Sinclair" <billsincl(a)aol.com> wrote in message <htjf70$oj3$1(a)fred.mathworks.com>...
> 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
From: Bill Sinclair on 27 May 2010 11:06
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <htkega$bvi$1(a)fred.mathworks.com>...
> "Bill Sinclair" <billsincl(a)aol.com> wrote in message <htjf70$oj3$1(a)fred.mathworks.com>...
> > 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

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
From: Roger Stafford on 27 May 2010 15:38
"Bill Sinclair" <billsincl(a)aol.com> wrote in message <htm1os$h2s$1(a)fred.mathworks.com>...
> 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
From: Bill Sinclair on 28 May 2010 11:02
"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.

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.......
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Orthogonal distance regression of parabolic data
Next: train neural network with wavelet feature