mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2022-05-08, 03:59   #1
pvaldivia
 
Mar 2022

17 Posts
Default 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.
pvaldivia is offline   Reply With Quote
Old 2022-05-11, 15:31   #2
pvaldivia
 
Mar 2022

100012 Posts
Default

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?
pvaldivia is offline   Reply With Quote
Old 2022-05-12, 10:14   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·17·293 Posts
Default

Quote:
Originally Posted by pvaldivia View Post
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
LaurV is offline   Reply With Quote
Old 2022-05-12, 15:34   #4
pvaldivia
 
Mar 2022

1116 Posts
Default

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!
pvaldivia is offline   Reply With Quote
Old 2022-05-12, 19:39   #5
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

11·89 Posts
Default

Have you had a look at mersenne.org's math page?
kruoli is online now   Reply With Quote
Old 2022-05-13, 22:45   #6
pvaldivia
 
Mar 2022

1116 Posts
Default

I hadn't when you posted, but that is very helpful. Thank you!
pvaldivia is offline   Reply With Quote
Old 2022-05-14, 02:29   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2×17×293 Posts
Default

Quote:
Originally Posted by pvaldivia View Post
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...
LaurV is offline   Reply With Quote
Old 2022-05-14, 16:28   #8
pvaldivia
 
Mar 2022

1116 Posts
Default

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.
pvaldivia is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:00.


Sat May 21 23:00:59 UTC 2022 up 37 days, 21:02, 0 users, load averages: 2.57, 1.77, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔