# A conjecture about mersenne primes and non-primes

Latest Edit: My hypothesis is simply that A056295(n) are spread around some smooth curve and higher than the curve if M(n) is a non-prime (and perhaps also even higher yet if M(n) has many factors rather than few) and lower if M(n) is a prime. The necklace thing below is just the justification.

Edit: I haven’t changed the question but I believe this formulation to be much easier to read. I hope this is legal here. The question is whether the conjecture is an indication that a Mersenme number is a prime or non-prime. Also I corrected the simplification process: 2*k=k and k=M(n)-k.

Consider

i) an n-bead open necklace using exactly two different colored beads. The necklace has a fixed orientation i.e. the first bead is indentified.

ii) a binary number of the same length as the necklace.

The number of the n-bead necklace structures are now $2^n-1$. Now observe that the colors may be permuted without changing the necklace structure. We have therefore $0=2^n-1$ in a certain sense that we might name “mod A”, short for the rules of OEIS A056295. This equality (mod A) implies that the number of structures was $2^n-1$.

We now close the necklace and consider a process which might lead us to the new number of necklace structures from the starting point $2^n-1=M(n)$ (mod A) where M(n) is the nth Mersenne number.

The number we search is given by OEIS A056295(n), but we find it through a process below: An example $n = 4$ and $2^4-1 =15$. Since 1110=111 (mod A) etc. it follows that that 2k=k so we only have to consider odd numbers. The other rule of simplification come from permuting colors so that 1101=0010 (mod A), i.e. $k = M(n)– k$ (mod A). Example 5=15-1-5=9=15-1-9=5, i.e. 5 is a stable state, and we arrive at 3 stable states for n=4.

My conjecture is now that when M(n) is a non-prime the reducing sequence is smaller, resulting most often in a “higher” number of stable states, i.e. A056295(n) than if M(n) is a prime. Also we might expect a "high" number of factors of non-prime M(n) to be reflected in a high value of A056295(n). “Higher” here means higher that the value of a smooth curve about which the A056295(n) numbers would be evenly distributed. The conjecture might give an indicator when M(n) is a prime or not. My problem is to find the smooth curve with my limited (non-existent) computer skills.

Below is the number of factors of A0563295(n) versus (ln(A056295(n)) minus the logarithmic interpolated valuess of the neighbors (ln(A056295(n+1) - ln(A056295(n-1))/2 (my very naive smooth curve). Also I have a line rather than points for which I apologize. If I had my reader's computer skills this question would have been settled long ago.

There is a pattern below but the conjecture is not based on a pattern but an idea.

In any case - the following lines are just a repetition:

Added later: if you want to save time, just go to my fourth comment below.

The presented conjecture emanates from a generalization of the 4 button riddle, reported on a (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 an intermediate investigation, about the description of the structure of such buttons in an 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 buttons in the riddle 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(=16-2 for the 4-wall or 4-button case), reducing them to the stable state under the two rules of simplification, which converts from a number to a generalized n-button booth (having the same number of states as a two color n-bead necklace). 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 states 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 sequence 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 series 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 is smaller resulting in a proportionally higher number of stable states, i.e. A056295(n) than if M(n) is a prime.

I tried 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(10) . Many of cases give a proportional higher number of states, if M(n) contains the factor 3. M(n) being 3*k implies that M(2n)-k = 2k =k, giving an extra stable state.

However, my test tool TR(n) becomes impractical as n grows. I suggested this conjecture to the Mersenne forum as a way of assisting in their work, but it doesn’t look like they gave it much notice.

Grateful for any ideas to test this – observe that it is based on an idea, not a pattern for small numbers.

-
That sequence indeed seems to be the one you're looking for. I find your conjecture hard to understand: "when $M(n)$ is a non-prime the reducing sequence is smaller resulting in a proportionally higher number of stable states, i.e. A056295(n) than if $M(n)$ is a prime" -- what does "proportionally higher" mean? I would have thought that it might mean something like what you call the test ratio; but you say that this becomes "impractical" -- it's unclear to me what you're trying to replace it with. – joriki May 23 '13 at 16:14
I need to check this again. However I see that I want to say that one might expect a "relatively" higher.. rather than proportionally higher. There is no ground for assuming any proportionality. – Mikael Jensen May 23 '13 at 21:37
I recall that I wanted to “normalize” the fast decreasing TR(n) perhaps by dividing with a smooth function for A056295(n). – Mikael Jensen May 23 '13 at 21:48
I recall that I wanted to change the test quantity to detect a relative high or relative low number of states, perhaps by instead dividing the number of states with with a smooth function for A056295(n). (I am not at ease with comment function) – Mikael Jensen May 23 '13 at 21:58
I have a new primitive text quantity TQ, 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 a perfect correlation between A056295(n)/TQ and the number of factors of 2^n-1 up to 10. That is good beginning. – Mikael Jensen May 29 '13 at 19:36