mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2022-02-04, 06:49   #1
Shen
 
Jan 2017

5 Posts
Default 2^(2^127-1)- 1, what's low boundary by trial factor?

I came to know that such number has been checked there is no prime factor below 5*10^51 by https://primes.utm.edu/mersenne/ . What's the latest result about the low boundary ? what's the suitable program to check it (by gpu or cpu)?

I am coding a new method based on probability for factor(2^p- 1),quite different with other famous algorithms. Thus I want to attack the cantor's conjecture.

Thanks for your valuable information.
Shen is offline   Reply With Quote
Old 2022-02-04, 11:13   #2
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23×431 Posts
Default

Quote:
Originally Posted by Shen View Post
I came to know that such number has been checked there is no prime factor below 5*10^51 by https://primes.utm.edu/mersenne/ . What's the latest result about the low boundary ? what's the suitable program to check it (by gpu or cpu)?

I am coding a new method based on probability for factor(2^p- 1),quite different with other famous algorithms. Thus I want to attack the cantor's conjecture.

Thanks for your valuable information.
The current limit of the trial division for M(M(127)) is 145P*M127 (1.45*10^17*M127, about 2.467*10^55), see http://www.doublemersennes.org/mm127.php

Prove or disprove the primality of M(M(127)) is very interesting, since it will disprove either Catalan–Mersenne number conjecture or the New Mersenne conjecture, if M(M(127)) is proved prime, then the New Mersenne conjecture would be disproved, since (2^M(127)+1)/3 is divisible by 886407410000361345663448535540258622490179142922169401, hence composite, and thus M(127) will be a counterexample of the New Mersenne conjecture, on the other hand, if M(M(127)) is proved composite, then the Catalan–Mersenne number conjecture would be disproved, since M(M(127)) is the next number after M(127) in the Catalan–Mersenne sequence, and since if c is composite then 2^c-1 is also composite, M(127) will be the largest prime in the Catalan–Mersenne sequence.

Last fiddled with by sweety439 on 2022-02-04 at 11:19
sweety439 is offline   Reply With Quote
Old 2022-02-04, 11:18   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22×72×17 Posts
Default

The limit is k=145P.

So the factor limit is:

2*k*p+1 = 2 * 145P * (2127-1) + 1 ~ 4.93*1055

Last fiddled with by ATH on 2022-02-04 at 11:19
ATH is offline   Reply With Quote
Old 2022-02-04, 11:58   #4
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23×431 Posts
Default

Quote:
Originally Posted by ATH View Post
So the factor limit is:

2*k*p+1 = 2 * 145P * (2127-1) + 1 ~ 4.93*1055
The factor limit should be k*p+1
sweety439 is offline   Reply With Quote
Old 2022-02-04, 12:20   #5
Shen
 
Jan 2017

5 Posts
Default

Thank you! sweety439,ATH.

according to http://www.doublemersennes.org/math.php, it seems that the limit should be 2*145P *(2^127-1) + 1.

Last fiddled with by Shen on 2022-02-04 at 12:45 Reason: add information
Shen is offline   Reply With Quote
Old 2022-02-04, 17:12   #6
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

22·7·19 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Prove or disprove the primality of M(M(127)) is very interesting, since it will disprove either Catalan–Mersenne number conjecture or the New Mersenne conjecture
Indeed interesting. But since Catalan only conjectured that they are "prime up to a certain limit" the first five might well be the only ones. So it might seem more probable that it is composite? Well, for almost all numbers this is true though. Maybe what I mean is rather, it would be less of a surprise if Catalan-Mersenne ended after 5 terms - which technically wouldn't even disprove it - than the New Mersenne conjecture being wrong?


I remember having read here once that in a series of double exponential numbers there is often only a limited number of primes. Where does this come from?

Last fiddled with by bur on 2022-02-04 at 17:17
bur is offline   Reply With Quote
Old 2022-02-04, 19:12   #7
charybdis
 
charybdis's Avatar
 
Apr 2020

2EC16 Posts
Default

Quote:
Originally Posted by bur View Post
I remember having read here once that in a series of double exponential numbers there is often only a limited number of primes. Where does this come from?
The Prime Number Theorem says that the probability that n is prime tends to 1/log(n) as n tends to infinity. If you have a sequence that grows doubly exponentially, then the denominators log(n) grow exponentially. The expected number of primes in the sequence will then be the sum of a geometric series, which converges. Hence we expect finitely many primes, though for most of these series there's no hope of being able to prove finiteness.

[Note: for some doubly exponential sequences, such as Fermat numbers, the lack of small factors means that the 1/log(n) is instead loglog(n)/log(n). This doesn't affect the convergence of the series.]

The Catalan-Mersenne sequence grows far faster than doubly exponentially. It almost certainly contains no primes other than the ones known.
charybdis is offline   Reply With Quote
Old 2022-02-04, 21:25   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×72×67 Posts
Default

Quote:
Originally Posted by sweety439 View Post
The factor limit should be k*p+1
Not sure why you drop the 2 there.
M(11)%23=0, k=1. Any factors of Mersenne numbers with prime exponents are of the form f = 2 k p + 1, where p is the prime exponent, and k is a natural number. https://primes.utm.edu/notes/proofs/MerDiv.html

From the end of my GTX1650 GPU mmff run to k=145P for MM127:
Code:
[Sep 10 21:38] M127        [185-186]:  99.6% 4596/4620,956/960 |   n.a.  | 554.12s | 36m56s | 191.52G | 345.63M/s | 1050165 |   n.a.%  | kriesel@emu/gtx1650
[Sep 10 21:47] M127        [185-186]:  99.7% 4597/4620,957/960 |   n.a.  | 554.00s | 27m42s | 191.52G | 345.70M/s | 1050165 |   n.a.%  | kriesel@emu/gtx1650
[Sep 10 21:56] M127        [185-186]:  99.8% 4600/4620,958/960 |   n.a.  | 554.16s | 18m28s | 191.52G | 345.60M/s | 1050165 |   n.a.%  | kriesel@emu/gtx1650
[Sep 10 22:05] M127        [185-186]:  99.9% 4605/4620,959/960 |   n.a.  | 554.13s |  9m14s | 191.52G | 345.62M/s | 1050165 |   n.a.%  | kriesel@emu/gtx1650
[Sep 10 22:15] M127        [185-186]: 100.0% 4617/4620,960/960 |   n.a.  | 554.23s |  0m00s | 191.52G | 345.56M/s | 1050165 |   n.a.%  | kriesel@emu/gtx1650
no factor for MM127 in k range: 144115188075855872 to 145000000000000000 (186-bit factors) [mmff 0.28 mfaktc_barrett188_M127gs]
Here M127=p = 127 bits
kmax = 145E15 ~ 57.0088 bits
f = 2 k p + 1 ~ 1 + 127 + 57+delta ~185+delta bits which mmff calls 186 bits, because that's what it takes to store or manipulate 185.xxxx bit of data.

MMFF 0.28 currently supports TF up to 188 bits for MM127. One of these years I'll get back to it.
https://mersenneforum.org/showpost.p...&postcount=382
kriesel is online now   Reply With Quote
Old 2022-02-05, 10:10   #9
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23×431 Posts
Default

Quote:
Originally Posted by kriesel View Post
Not sure why you drop the 2 there.
Well, see https://oeis.org/A001917, for any n, all prime factors of Phi(n,2)/gcd(Phi(n,2),n) (where Phi is the cyclotomic polynomial, if n is prime, then this number is the Mersenne number 2^n-1, and if n is power of 2, then this number is the Fermat number 2^(n/2)+1) (they are the primes p such that znorder(Mod(2,p)) = n) are of the form k*n+1

Code:
p   znorder(Mod(2,p))   k=(p-1)/znorder(Mod(2,p))
3,2,1
5,4,1
7,3,2
11,10,1
13,12,1
17,8,2
19,18,1
23,11,2
29,28,1
31,5,6
37,36,1
41,20,2
43,14,3
47,23,2
53,52,1
59,58,1
61,60,1
67,66,1
71,35,2
73,9,8
79,39,2
83,82,1
89,11,8
97,48,2
101,100,1
103,51,2
107,106,1
109,36,3
113,28,4
127,7,18
131,130,1
137,68,2
139,138,1
149,148,1
151,15,10
157,52,3
163,162,1
167,83,2
173,172,1
179,178,1
181,180,1
191,95,2
193,96,2
197,196,1
199,99,2
211,210,1
223,37,6
227,226,1
229,76,3
233,29,8
239,119,2
241,24,10
251,50,5
257,16,16
263,131,2
269,268,1
271,135,2
277,92,3
281,70,4
283,94,3
293,292,1
307,102,3
311,155,2
313,156,2
317,316,1
331,30,11
337,21,16
347,346,1
349,348,1
353,88,4
359,179,2
367,183,2
373,372,1
379,378,1
383,191,2
389,388,1
397,44,9
401,200,2
409,204,2
419,418,1
421,420,1
431,43,10
433,72,6
439,73,6
443,442,1
449,224,2
457,76,6
461,460,1
463,231,2
467,466,1
479,239,2
487,243,2
491,490,1
499,166,3
503,251,2
509,508,1
521,260,2
523,522,1
541,540,1
547,546,1
557,556,1
563,562,1
569,284,2
571,114,5
577,144,4
587,586,1
593,148,4
599,299,2
601,25,24
607,303,2
613,612,1
617,154,4
619,618,1
631,45,14
641,64,10
643,214,3
647,323,2
653,652,1
659,658,1
661,660,1
673,48,14
677,676,1
683,22,31
691,230,3
701,700,1
709,708,1
719,359,2
727,121,6
733,244,3
739,246,3
743,371,2
751,375,2
757,756,1
761,380,2
769,384,2
773,772,1
787,786,1
797,796,1
809,404,2
811,270,3
821,820,1
823,411,2
827,826,1
829,828,1
839,419,2
853,852,1
857,428,2
859,858,1
863,431,2
877,876,1
881,55,16
883,882,1
887,443,2
907,906,1
911,91,10
919,153,6
929,464,2
937,117,8
941,940,1
947,946,1
953,68,14
967,483,2
971,194,5
977,488,2
983,491,2
991,495,2
997,332,3
1009,504,2
1013,92,11
1019,1018,1
1021,340,3
1031,515,2
1033,258,4
1039,519,2
1049,262,4
1051,350,3
1061,1060,1
1063,531,2
1069,356,3
1087,543,2
1091,1090,1
1093,364,3
1097,274,4
1103,29,38
1109,1108,1
1117,1116,1
1123,1122,1
1129,564,2
1151,575,2
1153,288,4
1163,166,7
1171,1170,1
1181,236,5
1187,1186,1
1193,298,4
1201,300,4
1213,1212,1
1217,152,8
1223,611,2
1229,1228,1
1231,615,2
1237,1236,1
1249,156,8
1259,1258,1
1277,1276,1
1279,639,2
1283,1282,1
1289,161,8
1291,1290,1
1297,648,2
1301,1300,1
1303,651,2
1307,1306,1
1319,659,2
1321,60,22
1327,221,6
1361,680,2
1367,683,2
1373,1372,1
1381,1380,1
1399,233,6
1409,704,2
1423,237,6
1427,1426,1
1429,84,17
1433,179,8
1439,719,2
1447,723,2
1451,1450,1
1453,1452,1
1459,486,3
1471,245,6
1481,370,4
1483,1482,1
1487,743,2
1489,744,2
1493,1492,1
1499,1498,1
1511,755,2
1523,1522,1
1531,1530,1
1543,771,2
1549,1548,1
1553,194,8
1559,779,2
1567,783,2
1571,1570,1
1579,526,3
1583,791,2
1597,532,3
1601,400,4
1607,803,2
1609,201,8
1613,52,31
1619,1618,1
1621,1620,1
1627,542,3
1637,1636,1
1657,92,18
1663,831,2
1667,1666,1
1669,1668,1
1693,1692,1
1697,848,2
1699,566,3
1709,244,7
1721,215,8
1723,574,3
1733,1732,1
1741,1740,1
1747,1746,1
1753,146,12
1759,879,2
1777,74,24
1783,891,2
1787,1786,1
1789,596,3
1801,25,72
1811,362,5
1823,911,2
1831,305,6
1847,923,2
1861,1860,1
1867,1866,1
1871,935,2
1873,936,2
1877,1876,1
1879,939,2
1889,472,4
1901,1900,1
1907,1906,1
1913,239,8
1931,1930,1
1933,644,3
1949,1948,1
1951,975,2
1973,1972,1
1979,1978,1
1987,1986,1
1993,996,2
1997,1996,1
1999,333,6
2003,286,7
2011,402,5
2017,336,6
2027,2026,1
2029,2028,1
2039,1019,2
2053,2052,1
2063,1031,2
2069,2068,1
2081,1040,2
2083,2082,1
2087,1043,2
2089,29,72
2099,2098,1
2111,1055,2
2113,44,48
2129,532,4
2131,2130,1
2137,1068,2
2141,2140,1
2143,51,42
2153,1076,2
2161,1080,2
2179,726,3
2203,734,3
2207,1103,2
2213,2212,1
2221,2220,1
2237,2236,1
2239,1119,2
2243,2242,1
2251,750,3
2267,2266,1
2269,2268,1
2273,568,4
2281,190,12
2287,381,6
2293,2292,1
2297,1148,2
2309,2308,1
2311,1155,2
2333,2332,1
2339,2338,1
2341,780,3
2347,782,3
2351,47,50
2357,2356,1
2371,2370,1
2377,1188,2
2381,476,5
2383,397,6
2389,2388,1
2393,598,4
2399,1199,2
2411,482,5
2417,1208,2
2423,1211,2
2437,2436,1
2441,305,8
2447,1223,2
2459,2458,1
2467,2466,1
2473,618,4
2477,2476,1
2503,1251,2
2521,1260,2
2531,2530,1
2539,2538,1
2543,1271,2
2549,2548,1
2551,1275,2
2557,2556,1
2579,2578,1
2591,1295,2
2593,81,32
2609,1304,2
2617,1308,2
2621,2620,1
2633,1316,2
2647,1323,2
2657,166,16
2659,2658,1
2663,1331,2
2671,445,6
2677,2676,1
2683,2682,1
2687,79,34
2689,224,12
2693,2692,1
2699,2698,1
2707,2706,1
2711,1355,2
2713,1356,2
2719,1359,2
2729,1364,2
2731,26,105
2741,2740,1
2749,916,3
2753,1376,2
2767,461,6
2777,1388,2
2789,2788,1
2791,465,6
2797,2796,1
2801,1400,2
2803,2802,1
2819,2818,1
2833,118,24
2837,2836,1
2843,2842,1
2851,2850,1
2857,102,28
2861,2860,1
2879,1439,2
2887,1443,2
2897,1448,2
2903,1451,2
2909,2908,1
2917,972,3
2927,1463,2
2939,2938,1
2953,492,6
2957,2956,1
2963,2962,1
2969,371,8
2971,110,27
2999,1499,2
3001,1500,2
3011,3010,1
3019,3018,1
3023,1511,2
3037,3036,1
3041,1520,2
3049,762,4
3061,204,15
3067,3066,1
3079,1539,2
3083,3082,1
3089,772,4
3109,444,7
3119,1559,2
3121,156,20
3137,784,4
3163,1054,3
3167,1583,2
3169,1584,2
3181,1060,3
3187,3186,1
3191,55,58
3203,3202,1
3209,1604,2
3217,804,4
3221,644,5
3229,1076,3
3251,650,5
3253,3252,1
3257,407,8
3259,1086,3
3271,545,6
3299,3298,1
3301,660,5
3307,3306,1
3313,828,4
3319,1659,2
3323,3322,1
3329,1664,2
3331,222,15
3343,557,6
3347,3346,1
3359,1679,2
3361,168,20
3371,3370,1
3373,1124,3
3389,484,7
3391,113,30
3407,1703,2
3413,3412,1
3433,1716,2
3449,431,8
3457,576,6
3461,3460,1
3463,577,6
3467,3466,1
3469,3468,1
3491,3490,1
3499,3498,1
3511,1755,2
3517,3516,1
3527,1763,2
3529,882,4
3533,3532,1
3539,3538,1
3541,236,15
3547,3546,1
3557,3556,1
3559,1779,2
3571,3570,1
3581,3580,1
3583,1791,2
3593,1796,2
3607,601,6
3613,3612,1
3617,1808,2
3623,1811,2
3631,605,6
3637,3636,1
3643,3642,1
3659,3658,1
3671,1835,2
3673,918,4
3677,3676,1
3691,3690,1
3697,1848,2
3701,3700,1
3709,3708,1
3719,1859,2
3727,1863,2
3733,3732,1
3739,534,7
3761,188,20
3767,1883,2
3769,1884,2
3779,3778,1
3793,1896,2
3797,3796,1
3803,3802,1
3821,764,5
3823,637,6
3833,958,4
3847,1923,2
3851,3850,1
3853,3852,1
3863,1931,2
3877,3876,1
3881,388,10
3889,648,6
3907,3906,1
3911,1955,2
3917,3916,1
3919,1959,2
3923,3922,1
3929,1964,2
3931,3930,1
3943,219,18
3947,3946,1
3967,1983,2
3989,3988,1
4001,1000,4
4003,4002,1
4007,2003,2
4013,4012,1
4019,4018,1
4021,4020,1
4027,1342,3
4049,506,8
4051,50,81
4057,169,24
4073,2036,2
4079,2039,2
4091,4090,1
4093,4092,1
Also the factorization of Phi(n,2)

Last fiddled with by sweety439 on 2022-02-05 at 10:14
sweety439 is offline   Reply With Quote
Old 2022-02-05, 13:08   #10
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·72·67 Posts
Default

Hmm, for g = k n + 1, if kn is odd, for kn > 1, g is not a prime factor of anything, since it has a factor 2.
kriesel is online now   Reply With Quote
Old 2022-02-05, 13:54   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×31×47 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Well, see https://oeis.org/A001917, for any n, all prime factors of Phi(n,2)/gcd(Phi(n,2),n) (where Phi is the cyclotomic polynomial, if n is prime, then this number is the Mersenne number 2^n-1, and if n is power of 2, then this number is the Fermat number 2^(n/2)+1) (they are the primes p such that znorder(Mod(2,p)) = n) are of the form k*n+1
<snip>
Which has nothing to do with seeking odd prime factors q of 2p - 1 where p is an odd prime. At the risk of arrest for criminal belaboring of the obvious...

We want znorder(2,q) = p. Ergo, ipso facto, ex post facto, ex officio, etcetera etcetera etcetera,

(q-1)/znorder(2,q) = (q-1)/p is even.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Run trial factor faster tait1k27 Miscellaneous Math 2 2022-01-25 16:43
How many bits does/did the server trial factor to? Jayder Information & Answers 6 2015-01-25 03:29
Trial Factor Bit Depth lavalamp Operation Billion Digits 8 2010-08-02 18:49
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 05:40.


Tue Jun 28 05:40:30 UTC 2022 up 75 days, 3:41, 1 user, load averages: 0.84, 0.95, 1.04

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.

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