20020926, 16:22  #12  
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 
Quote:
p for the Mersenne exponent, rather than q (I believe this notation is more common; I used q for the exponent to be consistent with the notation used in the post i was replying to.) I encourage you to find other such correlations (e.g exponent mod 3, 5, 7,...) Ernst 

20040717, 21:13  #13  
Einyen
Dec 2003
Denmark
2·17·101 Posts 
E.W.Mayer wrote:
Quote:
Quote:


20040717, 21:16  #14 
Einyen
Dec 2003
Denmark
6552_{8} Posts 
Are there any restrictions for factors of Mersenne numbers Mq where q is not prime for both even and odd q?

20040719, 16:11  #15  
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
Quote:


20040720, 12:50  #16  
Banned
"Luigi"
Aug 2002
Team Italia
1001011111001_{2} Posts 
Quote:
Luigi 

20040724, 02:32  #17  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
Example: Originally, when Prime95 found a factor during trial factoring, it continued looking for a smaller factor during the uncompleted passes. (I.e., if it found a factor that was 7 mod 120, it continued looking in the 11 mod 120, 13 mod 120, ... and 119 mod 120 congruence classes.) One might decide that going to the morenumerous congruence classes mod 840 was not worth the side effect of having to trudge through the extra passes. It's not so much the teenytiny extra time involved as it is the psychological effect of users seeing it go through perhaps almost 100 more passes instead of only a dozen more. (I'm not saying this is a killer objection in particular. I'm saying this is an example of a side effect that deserved to be considered.) Also, once the mod 120 version had been tested and posted for use, changing to mod 840 or 9240 or whatever would require proportionally more testing and updating than they would have if originally used. Also, George W. considers the value to overall GIMPS throughput versus the required effort to make the change, in contrast to the value/effort ratios of a long list of other potential speedups. Last fiddled with by cheesehead on 20040724 at 02:41 

20040724, 14:00  #18 
Mar 2004
3×127 Posts 
Maybe there is a slight improvement, if you use 96 passes out of 840 or 960 passes out of 9240 instead of 16 out of 120. With that change you have 1/7 and 1/11 less candidates, but these are divisible by 7 and 11 and hence sieved in the first 2 loops anyway.
The only thing you get, is a little bit more dense sieving table, that you can put more candidates into the same space. Mathematically, the sieving gets more efficient, the bigger the sieving table gets, because the sieving limit can be higher. In the computer implementation, it is not recommended to define the table so large that the whole does not fit into the L1 cache. (I am pretty sure that George Woltman takes care of that). One possibility to optimize the sieving process is to define the size of the array to a size which is the product of the next few primes. For 840, the array would be 11*13*17 or so. In that array, the composite candidates can already be marked and the array can be copied, that it can be directly be taken for the next steps. If the copying is faster than deleting the array sieving these three primes, it will improve the whole a bit (A sieve is least efficient at small primes, because the steps are small and more of them are needed.) If we want to find factors as soon as possible, it makes sense to check the numbers in increasing order. Instead of finishing all stages for one bits, every stage can be sieved for 64 64.1 bit first then 64.1  64.2 bit and so on. If these steps are too small (that can happen if the number of stages is too high), the time penalty for switching the stages is too high and we gain nothing. Here, an optimum needs to be found. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
Modular restrictions on factors of Mersenne numbers  siegert81  Math  23  20140318 11:50 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 