20220812, 09:07  #45 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10,093 Posts 
Sorry, busy here around, I just looked for this thread, which you should read carefully, especially from post #32 onward, till the end.

20220812, 22:37  #46  
Jul 2022
7^{2} Posts 
Quote:
In addition you can calculate the possible remainders and automatically you can find the possible factors: Code:
tf_c(p,fromk=0,tok=10000)= { PrimesBase=[2,3,5,7,11]; n_PB=5; PrimesBaseProd=2; for(i=1,n_PB,PrimesBaseProd*=PrimesBase[i];); bW=2*p*PrimesBaseProd; RW=List(); listput(RW,1); for(i=1,PrimesBaseProd1,for(j=1,n_PB,;if(Mod(1+2*p*i,PrimesBase[j])^1==0,break;);if ((j==n_PB)&&(Mod(1+2*p*i,PrimesBase[j])^1!=0)&&(Mod(1+2*p*i,8)^1==1Mod(1+2*p*i,8)^1==7),listput(RW,1+2*p*i);););); nR=length(RW); for(k=fromk, tok, for(i=1,nR,q=RW[i]+bW*k; if(Mod(2,q)^p==1, if(q>1,print("M"p" has a factor: "q); break;));)); } Last fiddled with by User140242 on 20220812 at 22:38 

20220813, 03:56  #47 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10011101101101_{2} Posts 
Why would you do that? It will take a lot of time to build that list, and it will find a lot of unneeded composite factors which you need to factor later to find the real prime factors.

20220813, 06:24  #48  
Jul 2022
31_{16} Posts 
Quote:
You can use n_PB as a parameter and if you check the number of remainders that nR uses they are 2 if n_PB = 1, 4 if n_PB = 2, 16 if n_PB = 3, 96 if n_PB = 4 and 960 if n_PB = 5. That is, it is the same job as creating the table but you can perform an automatic operation as needed. Of course with this method it checks (tokfromk)*nR elements instead with forstep it checks (tokfromk)/nR elements but the factors are the same only the size of the interval changes. Finally, multiples of small factors can be easily eliminated for each row. Here you find an example with 2 classes and to speed up we use two vectors for the two classes: https://gist.github.com/user140242/0...d2738788bb1cae Last fiddled with by User140242 on 20220813 at 06:45 

20220813, 09:57  #49  
Jul 2022
7^{2} Posts 
Quote:
To extend the example for classes greater than 2 for each class we must use this: It is possible to eliminate the multiples of the small factors p_j>PrimesBase[n_PB] with p_j<bW and p_j!=p and p_j!=RW[n] for each RW[i] take a vector FACTOR of size dim_step+1 with dim_step=(tokfromk) initially set to True all multiples of p_j can be set to False in this way: Code:
r_t1=Euclidean_Diophantine(bW,p_j); //function return y in Diophantine equation bW * x + p_j * y = 1 r_t=(r_t1*RW[i])%bW; if (r_t>0) r_t=bW; C2=(bW+p_j)*r_t/bW; C1=r_tbW+p_j; for (m =bW+C1+C2; m<=dim_step && m>=0; m += p_j) FACTOR[m] = false; Code:
for(k=0;k<=dim_step;k++) if (FACTOR[k]) { D=RW[i]+bW*k; .... } Last fiddled with by User140242 on 20220813 at 10:15 

20220813, 10:15  #50  
"Καλός"
May 2018
3×11^{2} Posts 
Quote:
Quote:
I do not have a counterexample with p mod 6 = 5 that would result in a prime q = 2kp + 1 for k = 12m + 8 or 12m + 11 that divides 2^{p}  1. Currently, I am checking the known prime factors in the GIMPS database for a counterexample. Such a counterexample with p mod 6 = 5 could be rare or does not exist. 

20220813, 11:10  #51  
Apr 2020
3^{2}·5·19 Posts 
Quote:


20220814, 07:59  #52  
"Καλός"
May 2018
363_{10} Posts 
Quote:
Also, divisibility by 3 is observed for k = 12m + 5 since 2(12m + 5)(6n + 5) + 1 gives the coefficient 2×5×5 + 1 = 51 which is divisible by 3. Despite the equivalence between 2 mod 3 and 5 mod 6 (and between 1 mod 3 and 1 mod 6) for prime number considerations, I still use 'mod 6' for uniformity with a few other threads. What I am trying to evaluate is the additive dependence between the values of k for several factors for a given Mersenne number. On the basis of quite limited observations for k up to 11 (see posts #29 and #30), the values of k for another factor are obtained as follows:  the sum of a prime number (or 1) and 2^{n} such as 5 + 2^{2} = 3^{2} and 1 + 2^{3} = 3^{2};  the sum of 1 and a prime number giving 2^{n} such as 1 + 3 = 2^{2} and 1 + 7 = 2^{3};  the sum of two prime numbers giving 2^{n} such as 3 + 5 = 2^{3}; or  the sum of 2^{n} and a prime number giving a prime number such as 2^{2} + 3 = 7 and 2^{3} + 3 = 11. The exhaustive computations for k = 12 are ongoing. The custom source code was modified to collect data not only for p < 10^{9} but also for p < 2^{30}. 

20220817, 03:21  #53 
"Καλός"
May 2018
3·11^{2} Posts 
For k = 12, all possible pairs of two factors for a given Mersenne number are observed with Δk = 1, 3, 4, 5, 7, 8, 9, and 11, where Δk = k_{2}  k_{1} with k_{2} = 12 and k_{2} > k_{1}. No cases of three factors for a given Mersenne number are found.
For k = 13, only cases with Δk = 1, 4, 9, and 12 for a given Mersenne number are found, where Δk = k_{2}  k_{1} with k_{2} = 13 and k_{2} > k_{1}. Here 1 + 12 = 13 and 4 + 9 = 13. 
20220817, 07:37  #54  
Jul 2022
7^{2} Posts 
Quote:
if you use a basis bW=2*p*k we have for k = 12 = 2*2*3 q = r + bW*d where r are the possible remainders with 0 <= r <bW if we consider that q = 1 mod 2p then r = 1 mod 2p hence r = 1 + 2p*b with 0 <= b < k so for example if k = 12 and p = 29 the possible remainders are (1, 59, 117, 175, 233, 291, 349, 407, 465, 523, 581, 639) from these remainders you have to remove those that have factors in common with bW or remove the multiples of 3 since r = 1 mod 2p and since bW = 0 mod 8 we must consider that it must be r = 7 mod 8 or r = 1 mod 8 therefore remain (1, 175, 233, 407) so if you take the indices we find Δk or we consider (r1)/2/p (0,3,4,7) for p = 31 we find (1, 311, 497, 559) or (0, 5, 8, 9) for p = 37 we find (1, 223, 593, 815) or (0, 3, 8, 11) for p = 47 we find (1, 95, 377, 847) or (0, 1, 4, 9) as mentioned in a previous post there are 4 cases based on the value of p%4 and p%6 if k = 13 then bW is not divisible by 8 it is not convenient to use it in any case the procedure does not change surely you have forgotten some cases for example p=37 and q=223 then k1 = 3 and Δk = 133 = 10 Last fiddled with by User140242 on 20220817 at 08:24 

20220817, 10:10  #55  
"Καλός"
May 2018
3·11^{2} Posts 
Quote:
In the quoted example, 2^{37}1 = 137438953471, then 13743895347 / 223 = 616318177, and k_{2} = (6163181771)/(2×37) = 8328624, thus Δk = 8328624  3 = 8328621 = 3×7×396601, which is unrelated to k = 13. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Repeating residues in LL tests of composite Mersenne numbers  Viliam Furik  Number Theory Discussion Group  22  20201208 14:45 
Mersenne number with exponent 333333367 is composite  TheGuardian  GPU Computing  25  20190509 21:53 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 