mersenneforum.org Unfinished factoring puzzle
 Register FAQ Search Today's Posts Mark Forums Read

 2022-05-08, 03:59 #1 pvaldivia   Mar 2022 1116 Posts Unfinished factoring puzzle Hello, I'd like to ask another question of this forum: can the following be proven or disproven? Any tips or hints would be appreciated, or if you prefer to just post a solution, then by all means! Given a prime number p, define n= 2*(M(p-1)-1)/p. If we represent n as a binary number with p-1 bits, then if the digits of n are periodic with period q, and if q is prime, then prove/disprove that this implies that M(q) is divisible by p. For example, if p = 1399, then n= 2*(2^(1398)-1)/1399 is a very large number, and has periodicity 233 (when represented as a binary number with 1398 bits, including leading zeros). What I’d like to ask is whether it can be proven/disproven that knowing the periodicity (233 in this case) of n implies that M(233) is divisible by 1399. I am including some Python code in case anyone wants to use it to check behavior. In the code, lines 38-39 skip over primes p for which (p-7)*2+3 is also prime. The goal of proving the statement would be inclusive of those primes as well, but I thought it was important to show that this is not just that theorem reproduced, i.e. that there are additional primes p that this appears to work for. https://github.com/pvaldivia3/calculatePeriods In case anyone wants to take this as an “unfinished puzzle” I will block off an insight which begins to solve the problem (but doesn’t fully solve it), below. The one thought I’ve had thus far is to think about the representation of n/(2^233-1) as a binary decimal. I.e. 1/(2**233-1) as a binary decimal is just a decimal point followed by a repeating pattern of 232 zeros followed by a 1. Then if we multiply by n, then I believe we’ll get "something like" the representation of the repeating part of n in binary repeating every 233 digits (I say something like because, during the posting process, I am realizing that I may have made a logical error, yet I still think that "something like" may be true). If it could be proved that the reciprocal of that, i.e. (2^233-1)/(repeating part m of n) is an integer, then the proof would be complete. This feels similar to proving that in base 10, 0.999…. is equal to 1. Using a similar trick in binary "might give something like" (2^233-1)* (0.{m} repeating, where m is the repeating unit within n) = n, which doesn’t quite close the proof (again, the part in quotes reflects a logic error that I am realizing upon posting - I think "something like" is true but not certain). One final question, if this can be proven, would be: could it have any utility? Finding the period is not overly computationally burdensome, I don’t think. But it wouldn’t surprise me if the answer to the utility question, even if this were proved, would turn out to be no.
 2022-05-11, 15:31 #2 pvaldivia   Mar 2022 100012 Posts OK, I think I've found a proof. We start by guessing the answer and then showing that it's true. (2^(p-1)-1)/p ?= (2^(period)-1)/p [2^(period*(p-1)/period-1) + 2^(period*(p-1)/period-2)+2^(period*(p-1)/period-3) + .... + 2^ 0] Multiplying both sides by p, and distributing the period in the exponent, we get 2^(p-1)-1 ? = (2^period-1)[2^(p-1-period)+2^(p-1-2*period) + 2^(p-1-3*period) + ... + 2^0] Distributing the (2^(period-1)) on the RHS yields 2^(p-1)-1 = 2^(p-1)-1, thus proving the identity. I also updated the Github repo yesterday to do string comparison instead of character by character comparison. Also realized it wasn't necessary to include the factor of 2 in n. After testing with primes from the prime pages, the first 1000 of the 14th million primes from the below link took just under 27 minutes to produce the following results https://primes.utm.edu/lists/small/millions/ M39481417 is proposed to be divisible by 236888503 M13160479 is proposed to be divisible by 236888623 M29611181 is proposed to be divisible by 236889449 M10767829 is proposed to be divisible by 236892239 M29611607 is proposed to be divisible by 236892857 M259751 is proposed to be divisible by 236892913 M29611997 is proposed to be divisible by 236895977 M39482957 is proposed to be divisible by 236897743 M9870827 is proposed to be divisible by 236899849 M9870853 is proposed to be divisible by 236900473 M29612789 is proposed to be divisible by 236902313 M29612879 is proposed to be divisible by 236903033 M9871027 is proposed to be divisible by 236904649 M10768453 is proposed to be divisible by 236905967 Elapsed time is 1610.694779 seconds. And the first 1000 of the 50th million set, being about 4 times as large, took about 4 times as long, i.e. about two hours M40072883 is proposed to be divisible by 961749193 M68696477 is proposed to be divisible by 961750679 M564409 is proposed to be divisible by 961752937 M30054803 is proposed to be divisible by 961753697 M15027433 is proposed to be divisible by 961755713 M17810329 is proposed to be divisible by 961757767 M53431127 is proposed to be divisible by 961760287 M11183261 is proposed to be divisible by 961760447 M68697353 is proposed to be divisible by 961762943 M2862397 is proposed to be divisible by 961765393 M160294237 is proposed to be divisible by 961765423 M24044179 is proposed to be divisible by 961767161 M160294657 is proposed to be divisible by 961767943 M2081749 is proposed to be divisible by 961768039 M160294973 is proposed to be divisible by 961769839 Elapsed time is 6893.674706 seconds. I realize that this technique is different in that it doesn't directly find the a factor of the Mersenne of the prime you input, but rather finds a factor of the Mersenne prime lower than it. But I'd still like to ask the question of whether this can be of any utility in crossing off some potential Mersennes?
2022-05-12, 10:14   #3
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·5·23·29 Posts

Quote:
 Originally Posted by pvaldivia But I'd still like to ask the question of whether this can be of any utility in crossing off some potential Mersennes?
No, it is not. What you found out by calculus can be found in few seconds when "searching by q". There is a (well known) connection between the primality of the number, and the number of decimals in the period of its reciprocal.

Think about real (rational) numbers in base 2, which represent reciprocal of integers (in particular, reciprocals of mersenne numbers). The number of decimals in the period is unique only for prime mersenne. For example, 1/31 when represented in base 2, has 5 decimals in period, and there is no other reciprocal of a prime with 5 decimals in the period (why?). That shows that 31=2^5-1 is prime. If you compute 1/2047 in binary, there are 11 decimals in the period. As this is not unique, it means 2047=2^11-1 is not prime (hint: 1/23 and 1/89 both have 11 decimals in the period, too).

Mainly, your method is right, but you miss the fact that the numbers we use here is REALLY huge. To look for a factor of 2^p-1 you would need to do either ~p long divisions on p bits, or either 2^p-1 additions on p bits. That is because if you think how transforming in base 2 goes - you double the number and write down zeroes as long as the number is smaller than the divider, then, if it is larger than the divider, you write down a 1, subtract the divider, and repeat until you get the same remainder - this can be converted in a method where you start with 1, add your number to it, eliminate the tailing zeroes, than repeat, until you get 1 again, in this point you count the zeroes that you discarded, and you have your exponent and the factor.

For example, take 23, the procedure goes: 1, 24, 12, 6, 3, 26, 13, 36, 18, 9, 32, 16, 8, 4, 2, 1. When it grows, 23 was added. When it falls, a 0 was eliminated from the binary representation (i.e. if even, divide by 2). You eliminated 11 zeroes, therefore 2^11-1 is divisible by 23 (why?). This also says that 1/23 has 11 decimals in its period, when represented in base 2, because what I just did is the procedure of long division in base 2, but I just did it in reverse order (I show them in decimal to avoid writing long strings of 0 an 1, I did the transformation between base 2 and ten "on the fly" in my head ). This works for any odd number, not only for primes or mersenne numbers, for example, take 21, you have 1, 22, 11, 32, 16, 8, 4, 2, 1 - you cut 6 zeros, so 2^6-1 is divisible by 21.

It also looks very fast, just simple addition and shift, but in fact, if you remember the numbers we need to factor, this method did (with the usual notation, p is a prime, m=2^p-1, and q is a factor of m), maximum q additions on numbers of the size of 2*q. So, it depends on the size of the factors you find. Size of the factor, and not the number of digits in the factor. If the factor is 1 million, you do 1 million additions minus 1, in the worst case. Good luck finding any, say, 58 bits factors with this method. Or with your method, by the way (even much slower). All the factors you have shown are on the 30 bits range and can be found in milliseconds with current methods.

Last fiddled with by LaurV on 2022-05-12 at 10:28

 2022-05-12, 15:34 #4 pvaldivia   Mar 2022 17 Posts Thanks for this response - I had no idea that division would be the bottleneck! Also, since you mentioned current methods of finding factors of Mersenne numbers, are there references available that explain current methods at roughly an undergraduate level? P.S. I am totally jealous of your powers of instant mental conversion between base2 and base10!
 2022-05-12, 19:39 #5 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 2×3×181 Posts Have you had a look at mersenne.org's math page?
 2022-05-13, 22:45 #6 pvaldivia   Mar 2022 17 Posts I hadn't when you posted, but that is very helpful. Thank you!
2022-05-14, 02:29   #7
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

234258 Posts

Quote:
 Originally Posted by pvaldivia P.S. I am totally jealous of your powers of instant mental conversion between base2 and base10!
Haha, thank you for the praise, that was a joke, it was nothing to convert to base 2 there, or back to base 10 , everything runs in base 10, and it is even easier as it was presented. We know that even numbers have a 0 at the end, and eliminating that zero is the same as a division by 2.

But yes, I can convert small numbers between the two bases (or hex, or octal), mentally, and this comes with over 30 years of C and assembler programing. You probably, in your line of job, can also do some things that would totally surprise me...

 2022-05-14, 16:28 #8 pvaldivia   Mar 2022 17 Posts That is definitely an awesome power! One that I would use quite often. To your question, now that I think of it, I might have some anti-powers. The power of inefficient code and the power of forgotten vegetables are two that come to mind.

 Similar Threads Thread Thread Starter Forum Replies Last Post R2357 Puzzles 32 2020-10-16 19:24 Prime95 Programming 1 2017-05-13 16:01 Harrywill Puzzles 4 2017-05-03 05:10 henryzz Puzzles 4 2007-09-23 07:31 nibble4bits Puzzles 37 2006-02-27 09:35

All times are UTC. The time now is 18:22.

Wed Aug 10 18:22:22 UTC 2022 up 34 days, 13:09, 3 users, load averages: 1.53, 1.57, 1.41