20220508, 03:59  #1 
Mar 2022
17 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(p1)1)/p. If we represent n as a binary number with p1 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 3839 skip over primes p for which (p7)*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^2331) as a binary decimal. I.e. 1/(2**2331) 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^2331)/(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^2331)* (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. 
20220511, 15:31  #2 
Mar 2022
17 Posts 
OK, I think I've found a proof.
We start by guessing the answer and then showing that it's true. (2^(p1)1)/p ?= (2^(period)1)/p [2^(period*(p1)/period1) + 2^(period*(p1)/period2)+2^(period*(p1)/period3) + .... + 2^ 0] Multiplying both sides by p, and distributing the period in the exponent, we get 2^(p1)1 ? = (2^period1)[2^(p1period)+2^(p12*period) + 2^(p13*period) + ... + 2^0] Distributing the (2^(period1)) on the RHS yields 2^(p1)1 = 2^(p1)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? 
20220512, 10:14  #3  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 
Quote:
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^51 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^111 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^p1 you would need to do either ~p long divisions on p bits, or either 2^p1 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^111 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^61 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^p1, 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 20220512 at 10:28 

20220512, 15:34  #4 
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! 
20220512, 19:39  #5 
"Oliver"
Sep 2017
Porta Westfalica, DE
1,237 Posts 
Have you had a look at mersenne.org's math page?

20220513, 22:45  #6 
Mar 2022
11_{16} Posts 
I hadn't when you posted, but that is very helpful. Thank you!

20220514, 02:29  #7  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 
Quote:
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... 

20220514, 16:28  #8 
Mar 2022
11_{16} 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 antipowers. The power of inefficient code and the power of forgotten vegetables are two that come to mind.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A little puzzle  R2357  Puzzles  32  20201016 19:24 
SQL puzzle  Prime95  Programming  1  20170513 16:01 
Some puzzle  Harrywill  Puzzles  4  20170503 05:10 
4 4s puzzle  henryzz  Puzzles  4  20070923 07:31 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 