mersenneforum.org > Math Possible values for k (in Mersenne factors)
 Register FAQ Search Today's Posts Mark Forums Read

 2012-11-25, 16:17 #45 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 2×33×73 Posts As I'm working slowly through the ranges I'm starting to see some odd behaviour. Specifically, some ranges (of 10-million exponents) are finding approximately 15000 factors but other close ranges are only finding about half of that. For example: Code: Range Candidates Factored Unfactored Factors in 20000
2012-11-25, 16:57   #46
axn

Jun 2003

124638 Posts

Quote:
 Originally Posted by James Heinrich edit: the dropoffs are visible in the graph, notably the sharp drop around 2140M as noted above.
Just a guess: 2140M ~= 2^31, where things start to overflow 32 bit signed integer. All your factors for exponents above 2^31 are rubbish! Please recheck everything above 2147483648 /Just a Guess

Last fiddled with by axn on 2012-11-25 at 16:59

2012-11-25, 18:22   #47
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2×33×73 Posts

Quote:
 Originally Posted by axn Just a guess: 2140M ~= 2^31, where things start to overflow 32 bit signed integer. All your factors for exponents above 2^31 are rubbish! Please recheck everything above 2147483648 /Just a Guess
The cutoff point is suspiciously close to 2^31, but I'd be surprised if PARI (32-bit version notwithstanding) would stumble on that? For what it's worth, I'm using PARI both to generate the factors on my home computer, and then again to verify them upon submission to my server, and no factor has been rejected for being invalid.

As one check, I ran through 100 exponents at 2150M (that had been declared no-factor up to k=99999 by PARI) using mfaktc up to 2^65. I did find one small factor in that range that should have been caught, but for some reason was not. Unfortunately I've deleted the source file that was used to generate that range, but I'm re-creating it now...

<sudden flash of realization> :surprised

I think I may know the source of the problem... as stated elsewhere I'm using PHP to generate the PARI code, and I've moved the selection of jumplist from PARI code to the PHP generating code for a little runtime speedup. Unfortunately, the PHP installation on my server is 32-bit and so when I'm checking p%60 that is where failure enters the scene. For example, the missed factor I found with mfaktc in my test above (M2,150,001,863) should have 2,150,001,863 mod 60 = 23. To get real weird, PHP can fail in 2 different ways:
Code:
echo ('2150001863' % 60); = 7
echo (2150001863 % 60); = -53
I had put a check in to catch unexpected values, and would have caught the -53 version, but it was apparently evaluated as a string input which gave a valid (but incorrect) mod value, resulting in a wrong selection of the jump list.
Fortunately the gmp_mod function is available and will work correctly on any size exponent. So now I can re-generate all the work above 2^31.

So none of the generated factors above 2^31 were wrong, but about half of the factors were missed.
Thanks axn for the kick in the right direction.

 2012-11-26, 01:38 #48 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2·47·109 Posts If you use some code related to the one in post #37 (with 60 classes split) then you may not use the right starting value for k? (multiple of 60? 20000 is not multiple of 60, you have to start with 19980, or rotate the vectors accordingly) (also just a guess). edit: sorry, did not see your last post, I posted after axn's post (strange, the forum breaks the page at post #46, and I see post #47 as a new page, I am sure I selected 25 posts on page...) Last fiddled with by LaurV on 2012-11-26 at 01:44
2012-11-26, 01:44   #49
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts

Quote:
 Originally Posted by LaurV I am sure I selected 25 posts on page...)
No you didn't.

2012-11-26, 01:53   #50
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2×33×73 Posts

Quote:
 Originally Posted by LaurV If you use some code related to the one in post #37 (with 60 classes split) then you may not use the right starting value for k? (multiple of 60? 20000 is not multiple of 60, you have to start with 19980, or rotate the vectors accordingly) (also just a guess).
No, I got that part right at least. In my generating code I put in my target starting k (e.g. 20000) and then it automatically rounds it down until it's mod60=0 (19980 in this case, as you said).

But I've now regenerated my assignment files and it seems to be happily finding all the factors it was missing before, so I'm happy.

2013-01-02, 03:25   #51
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

F6616 Posts

Quote:
 Originally Posted by James Heinrich my plan is now to continue this up to k=100000 and squeeze a few more factors out. There's just slightly over 100-million candidates, and so far I'm getting about 4.8% factor rate, so I expect roughly 5-million factors at the end of this run. Candidate processing rate with PARI is approximately 5 candidates per second (per core). At this rate it'll take about 40 days (at 100% CPU and 24h/day, neither of which will actually happen, so probably about 100 real days).
It's done!

My two predictions were remarkably accurate. Today is 40 days after I posted that, and I found 5,099,114 factors using this method.
(disclaimer: that doesn't mean quite that many candidates were eliminated; those "extra" 100k factors probably accounts for the cases where multiple factors were found for k<100000)

Thanks again to everyone who helped me figure out this code.

 2014-04-11, 10:07 #52 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2·47·109 Posts Sorry that I am waking up this topic. I searched for it in the light of this new discussion, I did not get the right thing I was searching for, but reaching this topic remembers me that I had implemented the "420 classes" not long after this discussion, doing a pari script to generate the vectors. The code might be useful to somebody, so I will include here. It is about 15% faster than the "60 classes" code described in the posts above. It also eliminates the restriction that the starting q be a multiple of 420. The version with 4620 classes would be slower because of overhead (hey! pari is not mfaktc!). Somebody can use it for understanding how mfaktc works, or for TF-in small exponents which are outside of the mfaktc range (again, there are much faster programs there outside, this is not for "production" purposes). tf420.gp.txt [can't insert code, is over 10k characters limit] Last fiddled with by LaurV on 2014-04-11 at 10:14
 2014-04-11, 11:00 #53 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 2·33·73 Posts Naysayers suitably ignored... Thanks for your updated code. Yes, I'm still using your 60-class version even as I type this (taking 2000M-4000M from 251 to 252). I'll go re-generate my assignment files with the 420-class version -- thanks!
 2014-04-23, 20:10 #54 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 2×3×23×61 Posts same question for double mersenne numbers ? I know that the form 2*k*p+1 stays the same for p=2^q-1; but if I form MMq into 2*j*(2*l*q+1)+1 the k value for this becomes: Code: (2*l + 1/q)*j which forces j to be a multiple of q I believe , x*q; converting the k value to: Code: (2*q*l + 1)*x and: Code: (2*q*l + 1)*x + l` is the value of k for (2lq+1)*(2xq+1); is there anything else that should be said about this value. Last fiddled with by science_man_88 on 2014-04-23 at 20:41
2014-04-23, 21:57   #55
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

97×103 Posts

Quote:
 Originally Posted by science_man_88 ...q I believe...
"q I believe" is the new form of Q.E.D.?

 Similar Threads Thread Thread Starter Forum Replies Last Post tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44 ChriS Math 14 2006-04-12 17:36 asdf Math 17 2004-07-24 14:00 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 06:14.

Sat Dec 10 06:14:48 UTC 2022 up 114 days, 3:43, 0 users, load averages: 1.46, 1.27, 1.15