Missed small factors - Page 5

dswanson · 2003-11-20, 02:50

Looking at GP2's posting for Sept 1999 - Jan 2002, I'd say that the full range that should be re-factored is 5.977M to 6.030M. But it is suspicious that the list has many fewer factors between 6.000M and 6.030M than in the smaller range between 5.977M and 6.000M. I suspect the higher range will prove much less fruitful at yielding additional previously unknown factors. My guess is that whoever turned in the original invalid results was not the only one working on this range, so most of the factors were found the first time around.

5977031,62,53,8955262528047959
5977297,62,53,6726544627832489
5977747,62,55,19633824707094817
5983511,62,59,544276274394463441
5984137,62,55,23631125247373991
5984233,62,54,14191314853344361
5984851,62,57,137104776771873919
5985211,62,57,100762210054220353
5986597,62,55,20480718739962161
5987573,62,57,100842190923838937
5987819,62,53,8940154497852377
5988379,62,53,6811735073842249
5988769,62,55,27070515883553447
5988869,62,59,341544400059053497
5991899,62,58,161148544392067543
5995669,62,55,33938443076331929
5998627,62,54,15965394805274353
5999209,62,55,25030153820305897
-------------------------------------------------------------------
6009307,62,60,853003067076880801
6019603,62,57,137024179940485697
6020621,62,56,48921040896521551
6029299,62,60,601912015136403287

dswanson · 2003-11-20, 03:10

Ah ha! The miracles of backup tape! I found the spreadsheet I was maintaining while I was re-factoring the 7.019M - 7.055M range. I did more work than I remembered. It looks like I re-factored the whole range from 2^50 to 2^59. I found no factors between 2^50 and 2^52, but a total of 39 factors between 2^52 and 2^59. See attached spreadsheet if you are interested in the details.

Anyone who wants to continue factoring this range should start at 2^59.

[Blast! I'm not allowed to upload a .xls file. OK, converted to .txt, but lost the pretty graph that went with it]

dsouza123 · 2003-11-20, 04:40

You can zip the .xls file then you can attach it.
It will also be smaller

dswanson · 2003-11-20, 05:51

Doh!

Zipped file attached. Pretty graph is on 2nd sheet.

GP2 · 2003-11-20, 09:13

Quote:

Originally posted by garo
GP2,
great work. one more thing. Would it be useful to break the number of factors up on a per bit basis? And maybe increase the bin size?

I finally followed up this excellent suggestion.

As a simple first cut, I just looked at factors of 16 decimal digits or more.

This time I decided to count the number of binary digits (bits) instead, and limit them with both a minimum and maximum. Having a maximum helps eliminate P-1 factors which probably just add noise by being done inconsistently for different exponents.

By varying the bin sizes and the upper and lower bit limits, you can make all kinds of dips in the curves stand out.

In the example graph below, we see the dip at 5.98-6.00M is now still quite prominent when we limit the count to the number of factors of between 53 and 62 bits, but another nearly as deep dip occurs at 14.64 - 14.66M.

The dip around 21.9M in the previous graph is less noticeable here... but it reappears very prominently if you change the limits to 53-65 bits.

On the other hand, if you use a limit of 50-57 bits, a prominent dip occurs at 2.20 - 2.22 M (and also in other places)

So there's all kinds of variations you can play with... there do seem to be a number of other "islands of underfactoring".

garo · 2003-11-20, 19:35

Great work! I would think that separate graphs for each bit would be even better. i.e. for each bin find the number of factors of 53 bits, 54 bits and so on.

Also, it probably makes sense to limit this to 20M right now since significant factoring work over those bits still needs to be done. The on exception is 57 bits since everything in the database has been done to 57 bits.

Since a 1 bit bin may cause a lot of jerkiness in the graph the bin sizes in terms of number of exponents could be made larger.

This is going to give us some good info on TF error rates. Also, if we could get George to tell us what usernames submitted the results for the "bad" ranges, we could scrutinize other ranges assigned to those people with greater care.

In any case, I think that we need to be a bit conservative right now in doing factoring for numbers that have already been LL tested twice.

Finally, George made a change to P95 a couple of versions ago where a number which was incompletely factored but already LL tested once was only factored to one fewer bit depth during doublechecking.

i.e. Test=8755317,60,0 would cause the number to be TFed to 64 bits before the LL test whereas

DoubleCheck=8755317,60,0 would only take the TF to 63 bits since a factor would only save one test now.

Just to be kept in mind. A Tfed lots of numbers in the 13 and 14M range that had been inadequately TFed before but only brought them up to 64 bits becasue they had already been LL tested once. Actually I did not find any factors amongst those so I suspect someone did TF that range but never submitted the ersults. But that is another story...

GP2 · 2003-11-21, 00:55

For what it's worth, I re-trial-factored 14.64 - 14.66M to 56 bits without finding any new factors. Perhaps that second dip in the graph above is just noise?

GP2 · 2003-12-15, 17:30

In all, the following small factors (less than 62 bits) were found in the range 5.98M - 6.00M:

5980279,61,1940170984546252553
5980519,53,5940298383023833
5980669,59,330511045006988479
5981179,56,48656981074082729
5983091,58,154512024745900607
5983597,58,239091608379173591
5984569,55,20327751912960497
5984947,58,257261222699347817
5985611,58,249293665116931111
5986609,55,29540714099783687
5986889,53,6992859337170767
5988001,61,2268519234313284241
5988839,59,390011638669030841
5990147,53,5484105191882591
5991379,56,59174469648640561
5991533,60,616673546097743633
5991571,57,126747497127842663
5991829,55,25878834608324153
5996009,58,157213477394404247
5998073,57,94217753908538657
5998459,57,84125201201551463
5999699,56,42745345112937799

I'll post a couple more ranges in the Mersenne-aries subforum, for 5.97M and 6.00M

nfortino · 2003-12-18, 03:45

Quote:

Originally posted by GP2
For what it's worth, I re-trial-factored 14.64 - 14.66M to 56 bits without finding any new factors. Perhaps that second dip in the graph above is just noise?

I don't think so. Here is some more detailed data on the range in question:
Fields are exponet range,# factors 50-57 bits,#factors 58-62bits

14320000-14340000,82,63
14340000-14360000,85,70
14360000-14380000,71,58
14380000-14400000,102,63
14400000-14420000,92,68
14420000-14440000,88,53
14440000-14460000,82,74
14460000-14480000,96,58
14480000-14500000,77,57
14500000-14520000,79,71
14520000-14540000,90,72
14540000-14560000,78,78
14560000-14580000,87,65
14580000-14600000,92,56
14600000-14620000,68,80
14620000-14640000,85,76
14640000-14660000,82,43
14660000-14680000,91,68
14680000-14700000,85,63
14700000-14720000,101,65
14720000-14740000,93,66
14740000-14760000,87,74
14760000-14780000,97,74
14780000-14800000,79,73
14800000-14820000,94,64
14820000-14840000,84,76
14840000-14860000,93,67
14860000-14880000,85,61
14880000-14900000,83,70
14900000-14920000,76,66
14920000-14940000,78,61
14940000-14960000,90,70
14960000-14980000,79,68
14980000-15000000,99,58

Average 86.18,66.15

Notice there is no discrepancy until 58 bits, so it is understandable your test found nothing. I tried to test these to 58 bits, but I couldn't get FactorOverride to work, and I can't factor 488 exponents to 65 bits.

GP2 · 2003-12-18, 04:25

Well, I'll finish up factoring them to 57 bits just in case, and then maybe we can release this range for the Mersenne-aries.

I've been in touch with Will Edgington by e-mail and he probably has valuable information about gaps in trial-factoring... we should be able to make use of that to pinpoint the ranges and bit depths to look at.

nfortino · 2003-12-18, 17:31

I followed LMH instructions and made FactorOverride work. Unless anyone has an objection, I'll factor 14.64M-14.66M up to 2^58, assuming up to 2^57 has been done accurately.

2003-11-20, 02:50	#45
dswanson Aug 2002 2³·5² Posts	Looking at GP2's posting for Sept 1999 - Jan 2002, I'd say that the full range that should be re-factored is 5.977M to 6.030M. But it is suspicious that the list has many fewer factors between 6.000M and 6.030M than in the smaller range between 5.977M and 6.000M. I suspect the higher range will prove much less fruitful at yielding additional previously unknown factors. My guess is that whoever turned in the original invalid results was not the only one working on this range, so most of the factors were found the first time around. 5977031,62,53,8955262528047959 5977297,62,53,6726544627832489 5977747,62,55,19633824707094817 5983511,62,59,544276274394463441 5984137,62,55,23631125247373991 5984233,62,54,14191314853344361 5984851,62,57,137104776771873919 5985211,62,57,100762210054220353 5986597,62,55,20480718739962161 5987573,62,57,100842190923838937 5987819,62,53,8940154497852377 5988379,62,53,6811735073842249 5988769,62,55,27070515883553447 5988869,62,59,341544400059053497 5991899,62,58,161148544392067543 5995669,62,55,33938443076331929 5998627,62,54,15965394805274353 5999209,62,55,25030153820305897 ------------------------------------------------------------------- 6009307,62,60,853003067076880801 6019603,62,57,137024179940485697 6020621,62,56,48921040896521551 6029299,62,60,601912015136403287 Last fiddled with by dswanson on 2003-11-20 at 02:52

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
More missed factors	lycorn	Data	76	2015-04-23 06:07
Missed factors	TheMawn	Information & Answers	7	2014-01-10 10:23
Optimal Parameters for Small Factors	patrickkonsor	GMP-ECM	16	2010-09-28 20:19
Awfully small factors....	petrw1	Lone Mersenne Hunters	17	2009-11-20 03:40
Small factors	Kees	PrimeNet	6	2006-11-16 00:12

2003-11-20, 04:40	#47
dsouza123 Sep 2002 2·331 Posts	You can zip the .xls file then you can attach it. It will also be smaller

2003-11-20, 19:35	#50
garo Aug 2002 Termonfeckin, IE 2⁴×173 Posts	Great work! I would think that separate graphs for each bit would be even better. i.e. for each bin find the number of factors of 53 bits, 54 bits and so on. Also, it probably makes sense to limit this to 20M right now since significant factoring work over those bits still needs to be done. The on exception is 57 bits since everything in the database has been done to 57 bits. Since a 1 bit bin may cause a lot of jerkiness in the graph the bin sizes in terms of number of exponents could be made larger. This is going to give us some good info on TF error rates. Also, if we could get George to tell us what usernames submitted the results for the "bad" ranges, we could scrutinize other ranges assigned to those people with greater care. In any case, I think that we need to be a bit conservative right now in doing factoring for numbers that have already been LL tested twice. Finally, George made a change to P95 a couple of versions ago where a number which was incompletely factored but already LL tested once was only factored to one fewer bit depth during doublechecking. i.e. Test=8755317,60,0 would cause the number to be TFed to 64 bits before the LL test whereas DoubleCheck=8755317,60,0 would only take the TF to 63 bits since a factor would only save one test now. Just to be kept in mind. A Tfed lots of numbers in the 13 and 14M range that had been inadequately TFed before but only brought them up to 64 bits becasue they had already been LL tested once. Actually I did not find any factors amongst those so I suspect someone did TF that range but never submitted the ersults. But that is another story...

2003-11-21, 00:55	#51
GP2 Sep 2003 2×5×7×37 Posts	For what it's worth, I re-trial-factored 14.64 - 14.66M to 56 bits without finding any new factors. Perhaps that second dip in the graph above is just noise?

2003-12-15, 17:30	#52
GP2 Sep 2003 2×5×7×37 Posts	In all, the following small factors (less than 62 bits) were found in the range 5.98M - 6.00M: 5980279,61,1940170984546252553 5980519,53,5940298383023833 5980669,59,330511045006988479 5981179,56,48656981074082729 5983091,58,154512024745900607 5983597,58,239091608379173591 5984569,55,20327751912960497 5984947,58,257261222699347817 5985611,58,249293665116931111 5986609,55,29540714099783687 5986889,53,6992859337170767 5988001,61,2268519234313284241 5988839,59,390011638669030841 5990147,53,5484105191882591 5991379,56,59174469648640561 5991533,60,616673546097743633 5991571,57,126747497127842663 5991829,55,25878834608324153 5996009,58,157213477394404247 5998073,57,94217753908538657 5998459,57,84125201201551463 5999699,56,42745345112937799 I'll post a couple more ranges in the Mersenne-aries subforum, for 5.97M and 6.00M

2003-12-18, 04:25	#54
GP2 Sep 2003 101000011110₂ Posts	Well, I'll finish up factoring them to 57 bits just in case, and then maybe we can release this range for the Mersenne-aries. I've been in touch with Will Edgington by e-mail and he probably has valuable information about gaps in trial-factoring... we should be able to make use of that to pinpoint the ranges and bit depths to look at.

2003-12-18, 17:31	#55
nfortino Nov 2003 245₈ Posts	I followed LMH instructions and made FactorOverride work. Unless anyone has an objection, I'll factor 14.64M-14.66M up to 2^58, assuming up to 2^57 has been done accurately.