View Single Post
Old 2011-01-31, 15:41   #1

3×37×47 Posts
Default A conjecture about Mersenne primes and non-primes

These are some results emanating from a generalization of the 4 button riddle, reported on Wu’s riddle site: (You are trapped in a small phone booth shaped room. In the middle of each side of the room there is a hole. In each hole there is a push button that can be in either an off or on setting. You can't see in the holes but you can reach your hands in them and push the buttons. You can't tell by feel whether they are in the on or off position. You may stick your hands in any two holes at the same time and push neither, either, or both of the buttons as you please. Nothing will happen until you remove both hands from the holes. You succeed if you get all the buttons into the same position, after which time you will immediately be released from the room. Unless you escape, after removing your hands the room will spin around, disorienting you so you can't tell which side is which. How can you escape?) The input is from the riddle but I don't talk about the answer here only the desription of the structure of such buttons in a n-button room.

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.

I haven’t double-checked all my states and there are many similar series in the OEIS, but the one I looked up using my first number serie 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, i.e. A056295(n) than if M(n) is a prime.

I use the 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(8), 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 an extra stable state. 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)! I would like to “normalize” the fast decreasing TR(n) by dividing with a smooth function for A056295(n). I realize it would require a “mathematical microscope” to detect the few extra states of A056295(n).

I would be grateful if programming-skillful people 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.
  Reply With Quote