Missed small factors - Page 4

GP2 · 2003-11-19, 19:07

And some more:

Sept 1999 - Jan 2002

265717,54,50,581225118579473
287849,54,50,1012740255856913
810209,55,54,10341088524096359
883247,56,55,29816682687422537
897877,56,55,19150021555825753
2000249,58,57,101375910589712071
2048021,58,55,34639933180105241
4461059,60,58,158294570033378593
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
7019297,63,58,160100125459121849
7019893,62,56,62107521866259671
7020641,63,58,226230108157229263
7023629,62,59,492205916073561271
7023647,62,57,112326283569600313
7024183,62,57,75281736259707793
7024733,62,55,29837129629407577
7025987,63,57,74052063365823791
7027303,62,55,31090234297428433
7027567,62,55,31888123068147377
7028947,63,58,203918491658210359
7029317,62,55,21465848698662911
7029661,62,59,501549631512760559
7030039,62,53,8973079240373057
7030579,62,57,75820312605254449
7032251,62,58,196038012871693639
7032913,62,58,169277506207282943
7033963,62,57,100945633281264553
7034147,62,56,69336006101614849
7034249,62,58,181400783467404271
7034441,62,59,320361814247659447
7035709,62,55,32224115240930407
7036021,62,53,5722407010285223
7036409,62,59,321885922408857601
7036709,62,55,19317609414628879
7038679,62,55,33920433699810943
7039027,62,59,322282475092119119
7040287,62,58,256631935315919543
7040413,62,54,10139232364229593
7041469,62,53,8357369037658657
7041569,62,57,117357375956034911
7042069,62,55,20604362180778487
7042183,62,58,283427887358516321
7042207,62,53,7144472479359359
7042843,62,57,130606800742324631
7043041,62,56,46582254465212551
7043063,63,57,130921849537243591
7043339,62,56,46893453371703529
7044641,62,59,326445319708024481
7044803,62,54,12036732089312201
7044859,63,54,12518543901053329
7044881,62,55,35547469660129433
7045177,62,58,246277652069467831
7045537,62,53,4755424258607129
7045681,62,54,17165588884789937
7047041,62,56,67108943804505199
7047241,62,57,129735804329823841
7047311,62,59,329892805327791961
7049507,62,54,10611921631107647
7049789,62,53,6433401343966391
7050089,62,58,162743370549941359
7050619,62,61,1289161512938545471
7051069,62,56,67155536854413377
7051463,62,54,15219868713327361
7051757,62,54,10585089094320889
7054409,62,59,426257732962414817
7054447,62,53,5064200755979017
63539759,54,50,999387513942343
68787283,50,50,1081908536529127

Note that there's 265717 and 287849 to go with the recently discovered factor for 268813!

GP2 · 2003-11-19, 19:17

We should probably do some of the ranges suggested by the above data, but in an organized way to avoid duplication. Let's finish up the 5.98M range first.

PS,

Just now, I tried to trial-factor 250K exponents to 51 bits on a fast P4. To my astonishment, this takes much longer than factoring 5.98M exponents to 53 bits! More than 60 seconds each...

Can someone else try this and confirm it (maybe on another machine)? Garo?

Try these:
Factor=250037,0
Factor=250049,0
Factor=250051,0
Factor=250109,0
Factor=250153,0
Factor=250199,0
Factor=250301,0
Factor=250433,0
Factor=250451,0
Factor=250619,0

Time to dig out an older version of the program (or another program) to handle these???

smh · 2003-11-19, 19:36

Smaller exponents take longer to factor since every factor of a mersenne number must be of the form 2KP+1 where P is the prime exponent.

There are more possible candidates to test below a certain bit depth. 250K is 24 times smaller than 6M so tests would take about 24 times longer.

ET_ · 2003-11-19, 19:46

AFAIK, older versions of Prime95 just stopped when a factor was found.

On version 8 for instance there was a corrected "bug" that stopped and restarted factoring, corrected in version 10.

On version 14.2 a floating point round-off bugs in the factoring code that affected testing factors larger than 2^59 was corrected.

search for factors up to 2^64 was added on version 16.1

On version 16.4 a bug that prevented 486 & Cyrix machines from factoring above 2^62 has been fixed.

From version 19.0 factoring is now "layered", and trial factoring above 2^64 is now supported.

Finally, version 20.3: from whatsnew.txt, "Prime95 no longer searches for a smaller factor when trial factoring discovers a factor. The eeasons are two-fold. 1) Version 19 had a bug where stopping and restarting the program bypassed the search for smaller factors. Thus, my database may already be missing smaller factors. 2) As we factor larger exponents to a deeper depth it may no longer be a quick job to determine if there are smaller factors.
Note, that version 20 will still look for smaller factors if you are looking for factors below 2^60 with the FactorOverride option in undoc.txt.box."

Luigi

GP2 · 2003-11-19, 20:33

Quote:

Originally posted by ET_
AFAIK, older versions of Prime95 just stopped when a factor was found.

Yes but here we're not looking for smaller factors of exponents that already have a known factor.

We're looking for factors of exponents that don't have known factors, and that were supposedly trial-factored to a certain depth but were not, for some reason.

Perhaps the reason is some bugs in earlier versions of the software, like the ones you cite.

dsouza123 · 2003-11-19, 20:46

[Wed Nov 19 15:40:46 2003]
UID: dsouza123/0021, M250037 no factor to 2^40, WY1: 028201B0
UID: dsouza123/0021, M250049 no factor to 2^40, WY1: 027101B1
UID: dsouza123/0021, M250051 no factor to 2^40, WY1: 027301B3
UID: dsouza123/0021, M250109 no factor to 2^40, WY1: 027301AC
UID: dsouza123/0021, M250153 no factor to 2^40, WY1: 028201AC
UID: dsouza123/0021, M250199 no factor to 2^40, WY1: 027601AE
UID: dsouza123/0021, M250301 no factor to 2^40, WY1: 026801B1
UID: dsouza123/0021, M250433 no factor to 2^40, WY1: 027901B1
UID: dsouza123/0021, M250451 no factor to 2^40, WY1: 026E01AD
UID: dsouza123/0021, M250619 no factor to 2^40, WY1: 026801B0

Used Prime95 version 22.8 Athlon 1200, under a minute total.

GP2 · 2003-11-19, 22:00

Quote:

Originally posted by dsouza123
[Wed Nov 19 15:40:46 2003]
Used Prime95 version 22.8 Athlon 1200, under a minute total.

OK, now try it with FactorOverride bumped up to 51...

chalsall · 2003-11-19, 22:40

[Thu Nov 19 18:20:29 2003]
UID: wabbit/factoring, M250037 no factor to 2^52, WZ2: 028201B0
UID: wabbit/factoring, M250049 no factor to 2^52, WZ2: 027101B1
UID: wabbit/factoring, M250051 no factor to 2^52, WZ2: 027301B3
[Thu Nov 19 18:29:11 2003]
UID: wabbit/factoring, M250109 no factor to 2^52, WZ2: 027301AC
UID: wabbit/factoring, M250153 no factor to 2^52, WZ2: 028201AC
UID: wabbit/factoring, M250199 no factor to 2^52, WZ2: 027601AE
[Thu Nov 19 18:35:25 2003]
UID: wabbit/factoring, M250301 no factor to 2^52, WZ2: 026801B1
UID: wabbit/factoring, M250433 no factor to 2^52, WZ2: 027901B1
UID: wabbit/factoring, M250451 no factor to 2^52, WZ2: 026E01AD
[Thu Nov 19 18:41:41 2003]
UID: wabbit/factoring, M250619 no factor to 2^52, WZ2: 026801B0

Mersenne Prime Test Program, Version 23.5.2; Linux 2.4.21; AMD Duron 1.3GHz.

markr · 2003-11-19, 23:14

Definitely: the smaller the exponent, the longer the trial factoring time. And don't forget that P4s perform relatively poorly at TF below 62 bits - my timings are that a P4 1800MHz is about half as fast as an AMD XP 1540MHz.

dsouza123 · 2003-11-19, 23:36

Using FactorOverride=51 in prime.ini
Prime95 22.8 Athlon 1200 elapsed time 10:13 minutes

[Wed Nov 19 17:51:19 2003]
UID: dsouza123/0021, M250037 no factor to 2^51, WY1: 028201B0
UID: dsouza123/0021, M250049 no factor to 2^51, WY1: 027101B1
UID: dsouza123/0021, M250051 no factor to 2^51, WY1: 027301B3
UID: dsouza123/0021, M250109 no factor to 2^51, WY1: 027301AC
UID: dsouza123/0021, M250153 no factor to 2^51, WY1: 028201AC
[Wed Nov 19 17:56:59 2003]
UID: dsouza123/0021, M250199 no factor to 2^51, WY1: 027601AE
UID: dsouza123/0021, M250301 no factor to 2^51, WY1: 026801B1
UID: dsouza123/0021, M250433 no factor to 2^51, WY1: 027901B1
UID: dsouza123/0021, M250451 no factor to 2^51, WY1: 026E01AD
UID: dsouza123/0021, M250619 no factor to 2^51, WY1: 026801B0
[Wed Nov 19 18:01:32 2003]

garo · 2003-11-20, 01:43

smh has already posted the explanation. Smaller exponents do take proportionately longer to factor.

I guess the two ranges that should the focus of our efforts are 5.98 to 6.02M and the 7.02 to 7.05 M (ranges not precise - GP2 will probably determine the exact cutoffs).

For the remaining factors found - and great data mining GP2 btw - my guess is that at least some of them were due to hardware errors in machines. i.e. we do get false negatives from hot or unstable machines.

It is definitely not worth the effort to go do all the suspect exponent - and there really is no way to find out which ones are suspect. But one thing is clear. Machines that are bad for Ll tests may be bad for TF too. Having said that, we know that machines that produced bad LL results have given us correct factor. And we also know that the LL test pushes a machine way more than TF ever does. So the stability cutoff point is probably less strict for TF. But crazily overclocked machines that run very hot will likely produce bad TF results.

2003-11-19, 22:40	#41
chalsall If I May "Chris Halsall" Sep 2002 Barbados 2×11²×47 Posts	Range to 52. [Thu Nov 19 18:20:29 2003] UID: wabbit/factoring, M250037 no factor to 2^52, WZ2: 028201B0 UID: wabbit/factoring, M250049 no factor to 2^52, WZ2: 027101B1 UID: wabbit/factoring, M250051 no factor to 2^52, WZ2: 027301B3 [Thu Nov 19 18:29:11 2003] UID: wabbit/factoring, M250109 no factor to 2^52, WZ2: 027301AC UID: wabbit/factoring, M250153 no factor to 2^52, WZ2: 028201AC UID: wabbit/factoring, M250199 no factor to 2^52, WZ2: 027601AE [Thu Nov 19 18:35:25 2003] UID: wabbit/factoring, M250301 no factor to 2^52, WZ2: 026801B1 UID: wabbit/factoring, M250433 no factor to 2^52, WZ2: 027901B1 UID: wabbit/factoring, M250451 no factor to 2^52, WZ2: 026E01AD [Thu Nov 19 18:41:41 2003] UID: wabbit/factoring, M250619 no factor to 2^52, WZ2: 026801B0 Mersenne Prime Test Program, Version 23.5.2; Linux 2.4.21; AMD Duron 1.3GHz.

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-19, 19:07	#34
GP2 Sep 2003 2·5·7·37 Posts	And some more: Sept 1999 - Jan 2002 265717,54,50,581225118579473 287849,54,50,1012740255856913 810209,55,54,10341088524096359 883247,56,55,29816682687422537 897877,56,55,19150021555825753 2000249,58,57,101375910589712071 2048021,58,55,34639933180105241 4461059,60,58,158294570033378593 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 7019297,63,58,160100125459121849 7019893,62,56,62107521866259671 7020641,63,58,226230108157229263 7023629,62,59,492205916073561271 7023647,62,57,112326283569600313 7024183,62,57,75281736259707793 7024733,62,55,29837129629407577 7025987,63,57,74052063365823791 7027303,62,55,31090234297428433 7027567,62,55,31888123068147377 7028947,63,58,203918491658210359 7029317,62,55,21465848698662911 7029661,62,59,501549631512760559 7030039,62,53,8973079240373057 7030579,62,57,75820312605254449 7032251,62,58,196038012871693639 7032913,62,58,169277506207282943 7033963,62,57,100945633281264553 7034147,62,56,69336006101614849 7034249,62,58,181400783467404271 7034441,62,59,320361814247659447 7035709,62,55,32224115240930407 7036021,62,53,5722407010285223 7036409,62,59,321885922408857601 7036709,62,55,19317609414628879 7038679,62,55,33920433699810943 7039027,62,59,322282475092119119 7040287,62,58,256631935315919543 7040413,62,54,10139232364229593 7041469,62,53,8357369037658657 7041569,62,57,117357375956034911 7042069,62,55,20604362180778487 7042183,62,58,283427887358516321 7042207,62,53,7144472479359359 7042843,62,57,130606800742324631 7043041,62,56,46582254465212551 7043063,63,57,130921849537243591 7043339,62,56,46893453371703529 7044641,62,59,326445319708024481 7044803,62,54,12036732089312201 7044859,63,54,12518543901053329 7044881,62,55,35547469660129433 7045177,62,58,246277652069467831 7045537,62,53,4755424258607129 7045681,62,54,17165588884789937 7047041,62,56,67108943804505199 7047241,62,57,129735804329823841 7047311,62,59,329892805327791961 7049507,62,54,10611921631107647 7049789,62,53,6433401343966391 7050089,62,58,162743370549941359 7050619,62,61,1289161512938545471 7051069,62,56,67155536854413377 7051463,62,54,15219868713327361 7051757,62,54,10585089094320889 7054409,62,59,426257732962414817 7054447,62,53,5064200755979017 63539759,54,50,999387513942343 68787283,50,50,1081908536529127 Note that there's 265717 and 287849 to go with the recently discovered factor for 268813!

2003-11-19, 19:17	#35
GP2 Sep 2003 A1E₁₆ Posts	We should probably do some of the ranges suggested by the above data, but in an organized way to avoid duplication. Let's finish up the 5.98M range first. PS, Just now, I tried to trial-factor 250K exponents to 51 bits on a fast P4. To my astonishment, this takes much longer than factoring 5.98M exponents to 53 bits! More than 60 seconds each... Can someone else try this and confirm it (maybe on another machine)? Garo? Try these: Factor=250037,0 Factor=250049,0 Factor=250051,0 Factor=250109,0 Factor=250153,0 Factor=250199,0 Factor=250301,0 Factor=250433,0 Factor=250451,0 Factor=250619,0 Time to dig out an older version of the program (or another program) to handle these???

2003-11-19, 19:36	#36
smh "Sander" Oct 2002 52.345322,5.52471 29×41 Posts	Smaller exponents take longer to factor since every factor of a mersenne number must be of the form 2KP+1 where P is the prime exponent. There are more possible candidates to test below a certain bit depth. 250K is 24 times smaller than 6M so tests would take about 24 times longer.

2003-11-19, 19:46	#37
ET_ Banned "Luigi" Aug 2002 Team Italia 5·7·139 Posts	AFAIK, older versions of Prime95 just stopped when a factor was found. On version 8 for instance there was a corrected "bug" that stopped and restarted factoring, corrected in version 10. On version 14.2 a floating point round-off bugs in the factoring code that affected testing factors larger than 2^59 was corrected. search for factors up to 2^64 was added on version 16.1 On version 16.4 a bug that prevented 486 & Cyrix machines from factoring above 2^62 has been fixed. From version 19.0 factoring is now "layered", and trial factoring above 2^64 is now supported. Finally, version 20.3: from whatsnew.txt, "Prime95 no longer searches for a smaller factor when trial factoring discovers a factor. The eeasons are two-fold. 1) Version 19 had a bug where stopping and restarting the program bypassed the search for smaller factors. Thus, my database may already be missing smaller factors. 2) As we factor larger exponents to a deeper depth it may no longer be a quick job to determine if there are smaller factors. Note, that version 20 will still look for smaller factors if you are looking for factors below 2^60 with the FactorOverride option in undoc.txt.box." Luigi

2003-11-19, 20:46	#39
dsouza123 Sep 2002 2·331 Posts	[Wed Nov 19 15:40:46 2003] UID: dsouza123/0021, M250037 no factor to 2^40, WY1: 028201B0 UID: dsouza123/0021, M250049 no factor to 2^40, WY1: 027101B1 UID: dsouza123/0021, M250051 no factor to 2^40, WY1: 027301B3 UID: dsouza123/0021, M250109 no factor to 2^40, WY1: 027301AC UID: dsouza123/0021, M250153 no factor to 2^40, WY1: 028201AC UID: dsouza123/0021, M250199 no factor to 2^40, WY1: 027601AE UID: dsouza123/0021, M250301 no factor to 2^40, WY1: 026801B1 UID: dsouza123/0021, M250433 no factor to 2^40, WY1: 027901B1 UID: dsouza123/0021, M250451 no factor to 2^40, WY1: 026E01AD UID: dsouza123/0021, M250619 no factor to 2^40, WY1: 026801B0 Used Prime95 version 22.8 Athlon 1200, under a minute total.

2003-11-19, 23:14	#42
markr "Mark" Feb 2003 Sydney 3·191 Posts	Definitely: the smaller the exponent, the longer the trial factoring time. And don't forget that P4s perform relatively poorly at TF below 62 bits - my timings are that a P4 1800MHz is about half as fast as an AMD XP 1540MHz.

2003-11-19, 23:36	#43
dsouza123 Sep 2002 2×331 Posts	Using FactorOverride=51 in prime.ini Prime95 22.8 Athlon 1200 elapsed time 10:13 minutes [Wed Nov 19 17:51:19 2003] UID: dsouza123/0021, M250037 no factor to 2^51, WY1: 028201B0 UID: dsouza123/0021, M250049 no factor to 2^51, WY1: 027101B1 UID: dsouza123/0021, M250051 no factor to 2^51, WY1: 027301B3 UID: dsouza123/0021, M250109 no factor to 2^51, WY1: 027301AC UID: dsouza123/0021, M250153 no factor to 2^51, WY1: 028201AC [Wed Nov 19 17:56:59 2003] UID: dsouza123/0021, M250199 no factor to 2^51, WY1: 027601AE UID: dsouza123/0021, M250301 no factor to 2^51, WY1: 026801B1 UID: dsouza123/0021, M250433 no factor to 2^51, WY1: 027901B1 UID: dsouza123/0021, M250451 no factor to 2^51, WY1: 026E01AD UID: dsouza123/0021, M250619 no factor to 2^51, WY1: 026801B0 [Wed Nov 19 18:01:32 2003]

2003-11-20, 01:43	#44
garo Aug 2002 Termonfeckin, IE AD0₁₆ Posts	smh has already posted the explanation. Smaller exponents do take proportionately longer to factor. I guess the two ranges that should the focus of our efforts are 5.98 to 6.02M and the 7.02 to 7.05 M (ranges not precise - GP2 will probably determine the exact cutoffs). For the remaining factors found - and great data mining GP2 btw - my guess is that at least some of them were due to hardware errors in machines. i.e. we do get false negatives from hot or unstable machines. It is definitely not worth the effort to go do all the suspect exponent - and there really is no way to find out which ones are suspect. But one thing is clear. Machines that are bad for Ll tests may be bad for TF too. Having said that, we know that machines that produced bad LL results have given us correct factor. And we also know that the LL test pushes a machine way more than TF ever does. So the stability cutoff point is probably less strict for TF. But crazily overclocked machines that run very hot will likely produce bad TF results.