Possible values for k (in Mersenne factors) - Page 5

James Heinrich · 2012-11-25, 16:17

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<k<100000
2130M       464,860     156,532       308,328     15,644 
2140M       465,831     154,327       311,504     13,301 
2150M       465,334     147,582       317,752      7,336 
2160M       465,180     147,187       317,993      7,204

The lack of newly-found factors is not because factors have been previously found, you can see that there is really just fewer candidates factored in some ranges. I thought perhaps my code was misbehaving (which it yet might be), but running in other ranges there has been no dropoff in factor rate:

Code:

Range   Candidates    Factored    Unfactored   Factors in 20000<k<100000
1050M       481,207     169,206       312,001     16,183 
1060M       481,433     164,587       316,846     16,218 
1070M       480,645     164,706       315,939     16,263 
1080M       481,153     164,910       316,243     16,275 
                                    
1590M       471,866     160,013       311,853     15,984 
1600M       471,784     159,748       312,036     16,124 
1610M       471,178     159,317       311,861     15,697 
1620M       471,758     159,554       312,204     15,660

Any ideas why this might be?

edit: the dropoffs are visible in the graph, notably the sharp drop around 2140M as noted above.

axn · 2012-11-25, 16:57

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

James Heinrich · 2012-11-25, 18:22

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.

LaurV · 2012-11-26, 01:38

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...)

Dubslow · 2012-11-26, 01:44

Quote:

Originally Posted by LaurV

I am sure I selected 25 posts on page...)

No you didn't.

James Heinrich · 2012-11-26, 01:53

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.

James Heinrich · 2013-01-02, 03:25

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.

LaurV · 2014-04-11, 10:07

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]

James Heinrich · 2014-04-11, 11:00

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 2⁵¹ to 2⁵²).
I'll go re-generate my assignment files with the 420-class version -- thanks!

science_man_88 · 2014-04-23, 20:10

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.

Batalov · 2014-04-23, 21:57

Quote:

Originally Posted by science_man_88

...q I believe...

"q I believe" is the new form of Q.E.D.?

2012-11-25, 16:17	#45
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 2¹² 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<k<100000 2130M 464,860 156,532 308,328 15,644 2140M 465,831 154,327 311,504 13,301 2150M 465,334 147,582 317,752 7,336 2160M 465,180 147,187 317,993 7,204 The lack of newly-found factors is not because factors have been previously found, you can see that there is really just fewer candidates factored in some ranges. I thought perhaps my code was misbehaving (which it yet might be), but running in other ranges there has been no dropoff in factor rate: Code: Range Candidates Factored Unfactored Factors in 20000<k<100000 1050M 481,207 169,206 312,001 16,183 1060M 481,433 164,587 316,846 16,218 1070M 480,645 164,706 315,939 16,263 1080M 481,153 164,910 316,243 16,275 1590M 471,866 160,013 311,853 15,984 1600M 471,784 159,748 312,036 16,124 1610M 471,178 159,317 311,861 15,697 1620M 471,758 159,554 312,204 15,660 Any ideas why this might be? edit: the dropoffs are visible in the graph, notably the sharp drop around 2140M as noted above. Last fiddled with by James Heinrich on 2012-11-25 at 16:39 Reason: fixed: ranges are 10-million, not 1-million

2012-11-26, 01:38	#48
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 3·23·149 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

2014-04-11, 10:07	#52
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2829₁₆ 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-23, 20:10	#54
science_man_88 "Forget I exist" Jul 2009 Dartmouth NS 10000011100010₂ Posts	same question for double mersenne numbers ? I know that the form 2kp+1 stays the same for p=2^q-1; but if I form MMq into 2j(2lq+1)+1 the k value for this becomes: Code: (2l + 1/q)j which forces j to be a multiple of q I believe , xq; converting the k value to: Code: (2ql + 1)x and: Code: (2ql + 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44
A strange new (?) fact about Mersenne factors	ChriS	Math	14	2006-04-12 17:36
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

2014-04-11, 11:00	#53
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 2¹² 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 2⁵¹ to 2⁵²). I'll go re-generate my assignment files with the 420-class version -- thanks!