wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A conjecture about Mersenne primes and non-primes
        
(Message started by: Mickey1 on Jan 23^rd, 2011, 1:04am)

Title: A conjecture about Mersenne primes and non-primes
Post by Mickey1 on Jan 23^rd, 2011, 1:04am

These are some results emanating from a generalization of the 4 button riddle, the first part of which is reported elsewhere on the forum, under that heading. (Wu suggested another type of generalization which I was unable to follow. Frankly I guess is that many of his cases N>4 have no winning strategy at all with any number of hands; N=3 doesn’t seem to have any.)
The number of states of n buttons can be described by M(n) -2 in binary code, where M(n) is the Mersenne number 2^n-1, disregarding at first the cyclic arrangement of the buttons. The state of the 4 button trap room ranges from 0001 to 1110, omitting the two states 1111 and 0000, which let the trapped person out, according to the rules of the riddle.

Since the combinations are arranged cyclically, 0001=0010=0100=1000, i.e. 2k=k, where “=” here means “belongs to the same state”. Also k = M(n) -1 – k, since 0001=1110, according to the riddle rules (the buttons have no “on” or “off” states, only two different states).
Using the two rules of simplification, 2k=k and k = M(n) -1 – k, for our example n=4, we need to consider the states 1-14, reducing them to the stable state under the two rules of simplification. Since 2k=k we only need to consider the odd terms and the second rule implies that we only have to consider 1, 3, 5 and 7. But 7=15-7=8=4=2=1, so only 3 stable state remain, in their simplest binary form: 0001, 0011 and 0101. n=5 yields 15-5=10=5 and 3 =12=6=3. For n = 5, 6 and 7 the reduction series becomes increasingly neck-breaking, with very long reduction series for a non-programmer. And the stable number of states (excluding the two that let the person out) for n=1,2,3,4,5,6,7 are 0, 1, 1, 3, 3, 7, 9, the first term being perhaps philosophically problematic.

Caveats: I haven’t double-checked all my states and there are many similar series in the OEIS, but the one I looked up says: “A056295, Number of n-bead necklace structures using exactly two different colored beads.” It does look reasonable. It offers also the following higher states for n = 8 to 15: 19, 29, 55, 93, 179, 315, 595, 1095.

My conjecture is now that when M(n) is a non-prime the reducing sequence are smaller resulting in a proportionally higher number of stable states than if M(n) is a prime.
I use the (I assume you agree not-cherry-picking) test ratio TR(n): (the reduced states)/(all M(n)-2 states) or the nth number of A056295/(2^n-2). We have TR(2n-1)<TR(2n), or TR(1)<TR(2) (trivial perhaps), and it works for TR(3)<TR(4), TR(5)<TR(6), TR(7)<TR(eight), but TR(9)>TR(10) . Most of the even numbers cases give a proportional higher number of states, since M(2n) contains the factor 3. M(2n)=3*k (a “real” “=”) implies that M(n)-k = 2k =k, giving a stable state (I apologize for mixing the two meanings of “=”). This is also the case if M(n)=p1*p2, and p2=2^n+1, so that M(n)-p1=p1p2-p1=p1(p2-1), which would then be equal to p1, an extra stable state. Consider also Paganini’s M(11) for which TR(11)>TR(12)! If I “normalize” the fast decreasing TR(n) by dividing with a number from a straight line between TR(3) and TR(15) all the even/odd numbers come through but the effect from M(11) disappears. With access to a simple smooth formula for A056295 one could normalize the test quantity better and without bias.

I would be grateful if my programming-skillful co-riddlers could normalize or otherwise manage the effect of the fast decreasing series, and also look at some higher numbers. I call your attention to the service of the OEIS which gives a computer code for the series. I believe you have to admit at least that there is an effect for the even-odd ratio above in many cases, a heartwarming feature with my own background in cosmology. Cosmos also favor even (atomic numbers) to odd.

(In my version I a Smiley comes up instead of eight which I can't get rid of. I therefore use the word instead of the number)

Title: Re: A conjecture about Mersenne primes and non-pri
Post by Mickey1 on May 29^th, 2013, 1:32pm

I have a new primitive text quantity TQ, nearer to my goal - a smooth function for A056295(n) - which is simply the mean of the number for n-1 and n+1, i.e. TQ=(A056295(n−1)+A056295(n+1))/2 with which I compare A056295(n)

I find that there is an excellent correlation between A056295(n)/TQ and the number of factors of 2^n-1 up to 10. That is good beginning.

The attached graph show in a primitiv way the number of factors of 2^n-1 and the A056295(n) test quantity. They are - somewhat misleading - represented as continuous lines.