factors of Mersenne numbers

bhelmes · 2021-09-03, 00:51

A peaceful and pleasant night for you,

if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²-1
where n0 is the minimum, so that f | f(n0) and exactly one prime g with f*g=f(n0) where g<f

Is this a correct and (well known) logical statement ?

P.S. I am sure we find the next Mp before Christmas ...

Dr Sardonicus · 2021-09-03, 01:37

Quote:

Originally Posted by bhelmes

A peaceful and pleasant night for you,

if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²-1
where n0 is the minimum, so that f | f(n0) and exactly one prime g with f*g=f(n0) where g<f

Is this a correct and (well known) logical statement ?

Not true for Mersenne prime 2³ - 1 = 7: f = 7, n₀ = 3, n₀² - 2 = f.

True for Mersenne primes greater than 7: If p > 3 is prime, and P = 2^p - 1 is prime, then f = P, and f divides (2^((p+1)/2))^2 - 2 = 2*f. Here, g = 2.

Note that for p > 3, 2*2^((p+1)/2) = 2^((p+3)/2) < 2^((p+p)/2) = 2^p, so 2^((p+1)/2) <= P/2 = f/2, whence n₀ = 2^((p+1)/2).

Not necessarily true for composite values of 2^p - 1, p prime. Example: p = 11, 2¹¹ - 1 = 2047 = 23*89; f = 23, n₀ = 5, n₀² - 2 = f. No prime g < f here.

bhelmes · 2021-09-04, 21:29

The statement was not exactly formulated :

if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²-1
where n0 is the minimum, so that f | f(n0) and maximal one prime g with f*g=f(n0) where g<f

This statement would allow to limit the recursion deep of my algorithm.

Thanks if you spend me some lines.

P.S. I did some programming but the runtime has to improve further.

Dr Sardonicus · 2021-09-05, 01:53

Of course, since n₀ < f/2, the cofactor (2*n₀^2 - 1)/f < f/2. So if the cofactor is prime, it is certainly less than f.

Since I could think of no reason why the cofactor should always be prime, as a programming exercise I wrote a mindless script to look for counterexamples for 2^p - 1 with small prime exponent p.

I told it to print out the exponent p, the smallest factor f of 2^p - 1, the value n₀, and the factorization of the cofactor (2*n₀^2 - 1)/f when this was composite.

The smallest exponent giving a counterexample is p = 47. To my surprise, with the smallest example 47 (f = 2351, n₀ = 240) and 113 (f = 3391, n₀ = 700) the cofactor (2*n₀^2 - 1)/f is the square of a single prime. The smallest prime exponent for which the cofactor (2*n₀^2 - 1)/f has at least two distinct prime factors is 59.

Code:

? {
forprime(p=3,200,
M=factor(2^p-1);
f=M[1,1];
m=factormod(2*x^2-1,f);
n=lift(polcoeff(m[1,1],0,x));
if(n+n>f,n=f-n);
N=factor((2*n^2-1)/f);
if(#N[,1]>1||(#N[,1]==1&&N[1,2]>1),print(p" "f" "n" "N))
)
}
47 2351 240 Mat([7, 2])
59 179951 77079 [7, 1; 9433, 1]
67 193707721 66794868 [191, 1; 241177, 1]
71 228479 76047 [23, 1; 31, 1; 71, 1]
97 11447 5670 [41, 1; 137, 1]
101 7432339208719 3616686326055 [7, 1; 17, 1; 23, 1; 1583, 1; 812401, 1]
103 2550183799 270087243 [23, 1; 241, 1; 10321, 1]
109 745988807 298036466 [17, 1; 14008369, 1]
113 3391 700 Mat([17, 2])
137 32032215596496435569 6857964810884905735 [2503, 1; 358079, 1; 3276376633, 1]
151 18121 2513 [17, 1; 41, 1]
163 150287 31486 [79, 1; 167, 1]
173 730753 162850 [7, 1; 10369, 1]
179 359 170 [7, 1; 23, 1]
193 13821503 2664653 [7, 1; 146777, 1]
199 164504919713 50650852663 [7, 1; 4455809207, 1]
?

LarsNet · 2021-09-13, 00:58

Quote:

Originally Posted by Dr Sardonicus

Of course, since n₀ < f/2, the cofactor (2*n₀^2 - 1)/f < f/2. So if the cofactor is prime, it is certainly less than f.

Since I could think of no reason why the cofactor should always be prime, as a programming exercise I wrote a mindless script to look for counterexamples for 2^p - 1 with small prime exponent p.

I told it to print out the exponent p, the smallest factor f of 2^p - 1, the value n₀, and the factorization of the cofactor (2*n₀^2 - 1)/f when this was composite.

The smallest exponent giving a counterexample is p = 47. To my surprise, with the smallest example 47 (f = 2351, n₀ = 240) and 113 (f = 3391, n₀ = 700) the cofactor (2*n₀^2 - 1)/f is the square of a single prime. The smallest prime exponent for which the cofactor (2*n₀^2 - 1)/f has at least two distinct prime factors is 59.

Code:

? {
forprime(p=3,200,
M=factor(2^p-1);
f=M[1,1];
m=factormod(2*x^2-1,f);
n=lift(polcoeff(m[1,1],0,x));
if(n+n>f,n=f-n);
N=factor((2*n^2-1)/f);
if(#N[,1]>1||(#N[,1]==1&&N[1,2]>1),print(p" "f" "n" "N))
)
}
47 2351 240 Mat([7, 2])
59 179951 77079 [7, 1; 9433, 1]
67 193707721 66794868 [191, 1; 241177, 1]
71 228479 76047 [23, 1; 31, 1; 71, 1]
97 11447 5670 [41, 1; 137, 1]
101 7432339208719 3616686326055 [7, 1; 17, 1; 23, 1; 1583, 1; 812401, 1]
103 2550183799 270087243 [23, 1; 241, 1; 10321, 1]
109 745988807 298036466 [17, 1; 14008369, 1]
113 3391 700 Mat([17, 2])
137 32032215596496435569 6857964810884905735 [2503, 1; 358079, 1; 3276376633, 1]
151 18121 2513 [17, 1; 41, 1]
163 150287 31486 [79, 1; 167, 1]
173 730753 162850 [7, 1; 10369, 1]
179 359 170 [7, 1; 23, 1]
193 13821503 2664653 [7, 1; 146777, 1]
199 164504919713 50650852663 [7, 1; 4455809207, 1]
?

Dr. Sardonicus, i have found the all factors of mersenne primes follow a pattern that follows the bit_length() of the number which can be climbed from a starting number of the bit_length + the bit_length()-1 as shown in the quote below. At each climb you can do the tests inside the quote to check for a factor. This is obviously suboptimal and a faster way to generate the factors would be beneficial.

Just pointing this out as i found you post informing and wanted to point out the formula for generating the factors of prime numbers which are then used to create a mersenne number. You may already know this but just wanting to point it out to those interested in where those numbers ( factors ) come from.

On a side note, kind of wondering if trial division for mersenne numbers employ this climbing technique already as it chops out a lot of unnecessary tests

Quote:

Each OUT here can be tested as a factor of the mersenne via OUT*2+3 and (OUT+1)*2+3. and modding to see if the answer is zero. If you reach the sqrt of the number and no factors are found, then the mersenne is prime. Otherwise it had factors with a modulus of M[x]%(OUT*2) + 3 and M[x]%(OUT+1)*2+3.

In [3342]: 46+47 * 2
Out[3342]: 140

In [3343]: 140+47 * 2
Out[3343]: 234

In [3344]: 234+47 * 2
Out[3344]: 328

In [3345]: 328+47 * 2
Out[3345]: 422

In [3346]: 422+47 * 2
Out[3346]: 516

In [3347]: 516+47 * 2
Out[3347]: 610

In [3348]: 610+47 * 2
Out[3348]: 704

In [3349]: 704+47 * 2
Out[3349]: 798

In [3350]: 798+47 * 2
Out[3350]: 892

In [3351]: 892+47 * 2
Out[3351]: 986

In [3352]: 986+47 * 2
Out[3352]: 1080

In [3353]: 1080+47 * 2
Out[3353]: 1174

In [3354]: 1174*2+3
Out[3354]: 2351

Python CODE That does the above:

def getfactorsfromoffset2(n):
factors = []
x = gmpy2.mpz(31)
xr = gmpy2.bit_length(31)
r = gmpy2.bit_length(n)
jump = r - xr + 4
tsqrt = gmpy2.isqrt(n)
count = 0
while True and jump < tsqrt:

sjo = ( jump + r - 1 ) % n
sjt = ( jump + r*2 ) % n
jump = sjt
if n%(((sjo+1)*2)+3) == 0:
print(count, (sjo+1)*2+3, "Factor Found")

break
elif n%(((sjt)*2)+3) == 0:
print(count, (sjt)*2+3, "Factor Found")
break
#r *= 2 % sjt
##if count > 15000: break
count+=1

In [3366]: getfactorsfromoffset2(2**43-1)
1 431 Factor Found Offset for each jump is bit_length 43

In [3367]: getfactorsfromoffset2(2**53-1)
29 6361 Factor Found Offset for each jump is bit_length 53

In [3368]: getfactorsfromoffset2(2**67-1)
722789 193707721 Factor Found Offset for each jump is bit_length 67

In [3391]: getfactorsfromoffset2(2**55-1)
3 881 Factor Found Offset for each jump is bit_length 55

In [3392]: getfactorsfromoffset2(2**57-1)
141 32377 Factor Found Offset for each jump is bit_length 57

In [3393]: getfactorsfromoffset2(2**59-1)
761 179951 Factor Found Offset for each jump is bit_length 59

In [3394]: getfactorsfromoffset2(2**63-1)
367 92737 Factor Found Offset for each jump is bit_length 63

In [3395]: getfactorsfromoffset2(2**65-1)
30 8191 Factor Found Offset for each jump is bit_length 65

In [3396]: getfactorsfromoffset2(2**67-1)
722789 193707721 Factor Found Offset for each jump is bit_length 67

In [3372]: getfactorsfromoffset2(2**33-1)
14 2047 Factor Found Offset for each jump is bit_length 33

In [3373]: getfactorsfromoffset2(2**35-1)
877 122921 Factor Found Offset for each jump is bit_length 35

In [3374]: getfactorsfromoffset2(2**37-1)
0 223 Factor Found Offset for each jump is bit_length 37

In [3375]: getfactorsfromoffset2(2**39-1)
51 8191 Factor Found Offset for each jump is bit_length 39

In [3376]: getfactorsfromoffset2(2**41-1)
80 13367 Factor Found Offset for each jump is bit_length 41

In [3377]: getfactorsfromoffset2(2**43-1)
1 431 Factor Found Offset for each jump is bit_length 43

In [3378]: getfactorsfromoffset2(2**45-1)
2 631 Factor Found Offset for each jump is bit_length 45

In [3379]: getfactorsfromoffset2(2**47-1)
11 2351 Factor Found Offset for each jump is bit_length 47

LaurV · 2021-09-13, 02:49

Quote:

Originally Posted by LarsNet

Dr. Sardonicus, i have found the all factors of mersenne primes follow a pattern <...>

We all know this. All factors of mersenne primes follow the next pattern, if you exclude the number itself: 1, 1, 1, 1, 1, 1, .... (51 times).

Dr Sardonicus · 2021-09-13, 14:18

Quote:

Originally Posted by LarsNet

Dr. Sardonicus, i have found the all factors of mersenne primes follow a pattern that follows the bit_length() of the number which can be climbed from a starting number of the bit_length + the bit_length()-1 as shown in the quote below.

Assuming your code is supposed to do trial division of 2^k - 1 for odd k by numbers congruent to 1 (mod 2k) (and maybe it's just me, but I found your code to be excessively obscure), I note the following:

1) If k is odd and composite, not all prime factors of 2^k - 1 are congruent to 1 (mod 2k). If d|k, the prime factors of the "primitive part" of $\Phi_{d}$2$$ are congruent to 1 (mod 2d). They do not have to be congruent to 1 (mod 2k). For example, the factor 2^3 - 1 = 7 of 2^39 - 1 is congruent to 1 (mod 6) but not congruent to 1 (mod 78); and the factor 2^5 - 1 = 31 of 2^65 - 1 is congruent to 1 (mod 10) but not congruent to 1 (mod 65).

2) If p is an odd prime, it is well known that the prime factors of 2^p - 1 are congruent to 1 (mod 2p), and also congruent to 1 or 7 (mod 8).

3) If p is of any size at all, trial division up to the square root of 2^p - 1 is totally impracticable.

4) Also, if p is of any size at all, the number of candidates q == 1 (mod 2p) and 1 or 7 (mod 8) can be reduced significantly by excluding those with small prime factors.

I incorporated the facts in (2) into an otherwise totally mindless Pari-GP script. I wrote the script in a text editor and filled in the exponent by hand for each run, and copy-pasted it into a Pari-GP session. I didn't bother trying to code user input.

Code:

 {
p = 67;
n = 2^p - 1;
q=1;
r=p%4;
r=4-r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0||c>1000000,
q+=d;
c++;
d=a-d;
m=n%q;
if(m==0,
print("Try number "c" found the factor "q" of 2^"p" - 1.")
);
if(c>1000000,print("No factors found in a million tries."))
)
}
Try number 722790 found the factor 193707721 of 2^67 - 1.
? {
p = 101;
n = 2^p - 1;
q=1;
r=p%4;
r=4-r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0||c>1000000,
q+=d;
c++;
d=a-d;
m=n%q;
if(m==0,
print("Try number "c" found the factor "q" of 2^"p" - 1.")
);
if(c>1000000,print("No factors found in a million tries."))
)
}
No factors found in a million tries.
?

LarsNet · 2021-09-13, 15:34

Quote:

Originally Posted by Dr Sardonicus

Assuming your code is supposed to do trial division of 2^k - 1 for odd k by numbers congruent to 1 (mod 2k) (and maybe it's just me, but I found your code to be excessively obscure), I note the following:

My code definitely finds it for 67:

In [3396]: getfactorsfromoffset2(2**67-1)
722789 193707721 Factor Found Offset for each jump is bit_length 67

I'll look at installing pari gp see if i can follow what your doing

EDIT, oh there is this cool online interpreter at the pari/gp site, i'll look at that first

kriesel · 2021-09-13, 17:58

Maybe read through this too.

LarsNet · 2021-09-13, 18:28

While i'm learning PARI/GP, i added a runnable version of this on replit:

https://replit.com/@oppressionslyr/M...arison#main.py

You can change the bottom number to other numbers other than 2**43-1 and hit run again. This is not using gmpy2 (so is slow) and will not work with 2**49-1 since 127 factor is lower , than the first equations answer of (46+47-1)*2+3 and ((46+47-1)+1)*2+3. I'm sure i could tweak the offset to fix that if needed. My suggestion is to stay below 2**71-1, just because it's slow for larger numbers

THIS VERSION finds all factors instead of the first which i posted, all climbing from the same offset of the bit_length()

LarsNet · 2021-09-13, 18:53

Quote:

Originally Posted by kriesel

Maybe read through this too.

kriesel, it sounds like they do something similar to what i found, just not the same starting point maybe, does that sound correct? I jump the bit_level for each next factor so if i'm starting out:

Like this :

Quote:

In [17]: getfactorsfromoffset2(2**29-1)

count, jump, formula to generate prime, and
0 56 117 Factor Not Found
0 86 175 Factor Not Found
1 114 233 Factor Found
1 144 291 Factor Not Found
2 172 349 Factor Not Found
2 202 407 Factor Not Found
3 230 465 Factor Not Found
3 260 523 Factor Not Found
4 288 581 Factor Not Found
4 318 639 Factor Not Found
5 346 697 Factor Not Found
5 376 755 Factor Not Found
6 404 813 Factor Not Found
6 434 871 Factor Not Found
7 462 929 Factor Not Found
7 492 987 Factor Not Found
8 520 1045 Factor Not Found
8 550 1103 Factor Found
9 578 1161 Factor Not Found
9 608 1219 Factor Not Found
10 636 1277 Factor Not Found
10 666 1335 Factor Not Found
11 694 1393 Factor Not Found
11 724 1451 Factor Not Found
12 752 1509 Factor Not Found
12 782 1567 Factor Not Found
13 810 1625 Factor Not Found
13 840 1683 Factor Not Found
14 868 1741 Factor Not Found
14 898 1799 Factor Not Found
15 926 1857 Factor Not Found
15 956 1915 Factor Not Found
16 984 1973 Factor Not Found
16 1014 2031 Factor Not Found
17 1042 2089 Factor Found

So our 17th iteration is already at 1042.

...

Sorry if i posted something well known, i discovered this without knowing it, so thought it was useful. Also, would mine not be twice as fast due to the equation i use to get the larger number prime quicker, i'm actually ahead of the jump by the exponent by a factor of 2, lol

Just go with me on this, if you look at the right column, i'm jumping by twice the exponent and arriving at correct answers, that second column moves up by twice the bit_length or exponent which are the same. Maybe thats different? I wish i knew how to do emoticons, i'd put one here, that seems cool. I'm really not trying to sound like i've found anything revolutionary here, its just fun to point out ( which probably means my math is wrong, i'll look into that ( which it is i just verified, i should be looking at twice the bit_length and i'm looking at double it )

2021-09-03, 00:51	#1
bhelmes Mar 2016 431 Posts	factors of Mersenne numbers A peaceful and pleasant night for you, if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²-1 where n0 is the minimum, so that f \| f(n0) and exactly one prime g with f*g=f(n0) where g<f Is this a correct and (well known) logical statement ? P.S. I am sure we find the next Mp before Christmas ...

2021-09-05, 01:53	#4
Dr Sardonicus Feb 2017 Nowhere 2⁴·3·7·19 Posts	Of course, since n₀ < f/2, the cofactor (2n₀^2 - 1)/f < f/2. So if the cofactor is prime, it is certainly less than f. Since I could think of no reason why the cofactor should always be prime, as a programming exercise I wrote a mindless script to look for counterexamples for 2^p - 1 with small prime exponent p. I told it to print out the exponent p, the smallest factor f of 2^p - 1, the value n₀, and the factorization of the cofactor (2n₀^2 - 1)/f when this was composite. The smallest exponent giving a counterexample is p = 47. To my surprise, with the smallest example 47 (f = 2351, n₀ = 240) and 113 (f = 3391, n₀ = 700) the cofactor (2n₀^2 - 1)/f is the square of a single prime. The smallest prime exponent for which the cofactor (2n₀^2 - 1)/f has at least two distinct prime factors is 59. Code: ? { forprime(p=3,200, M=factor(2^p-1); f=M[1,1]; m=factormod(2x^2-1,f); n=lift(polcoeff(m[1,1],0,x)); if(n+n>f,n=f-n); N=factor((2n^2-1)/f); if(#N[,1]>1\|\|(#N[,1]==1&&N[1,2]>1),print(p" "f" "n" "N)) ) } 47 2351 240 Mat([7, 2]) 59 179951 77079 [7, 1; 9433, 1] 67 193707721 66794868 [191, 1; 241177, 1] 71 228479 76047 [23, 1; 31, 1; 71, 1] 97 11447 5670 [41, 1; 137, 1] 101 7432339208719 3616686326055 [7, 1; 17, 1; 23, 1; 1583, 1; 812401, 1] 103 2550183799 270087243 [23, 1; 241, 1; 10321, 1] 109 745988807 298036466 [17, 1; 14008369, 1] 113 3391 700 Mat([17, 2]) 137 32032215596496435569 6857964810884905735 [2503, 1; 358079, 1; 3276376633, 1] 151 18121 2513 [17, 1; 41, 1] 163 150287 31486 [79, 1; 167, 1] 173 730753 162850 [7, 1; 10369, 1] 179 359 170 [7, 1; 23, 1] 193 13821503 2664653 [7, 1; 146777, 1] 199 164504919713 50650852663 [7, 1; 4455809207, 1] ?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factors for the differences between Mersenne numbers	a nicol	Miscellaneous Math	1	2020-10-15 09:53
factors of Mersenne numbers	bhelmes	Miscellaneous Math	8	2020-09-14 17:36
Mersenne Prime Factors of v.large numbers	devarajkandadai	Miscellaneous Math	6	2006-01-04 22:44
Factors of Mersenne Numbers	asdf	Math	17	2004-07-24 14:00
Factors of Mersenne numbers ?	Fusion_power	Math	13	2003-10-28 20:52

2021-09-04, 21:29	#3
bhelmes Mar 2016 431 Posts	The statement was not exactly formulated : if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²-1 where n0 is the minimum, so that f \| f(n0) and maximal one prime g with f*g=f(n0) where g<f This statement would allow to limit the recursion deep of my algorithm. Thanks if you spend me some lines. P.S. I did some programming but the runtime has to improve further.

2021-09-13, 17:58	#9
kriesel "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 2²×3×643 Posts	Maybe read through this too.

2021-09-13, 18:28	#10
LarsNet Mar 2021 101100₂ Posts	While i'm learning PARI/GP, i added a runnable version of this on replit: https://replit.com/@oppressionslyr/M...arison#main.py You can change the bottom number to other numbers other than 243-1 and hit run again. This is not using gmpy2 (so is slow) and will not work with 249-1 since 127 factor is lower , than the first equations answer of (46+47-1)2+3 and ((46+47-1)+1)2+3. I'm sure i could tweak the offset to fix that if needed. My suggestion is to stay below 2**71-1, just because it's slow for larger numbers THIS VERSION finds all factors instead of the first which i posted, all climbing from the same offset of the bit_length()