Anyone factoring <5M? - Page 9

lorgix · 2010-11-15, 09:30

Quote:

Originally Posted by garo

In what range? It is generally agreed that it is not worth the effort to refactor all ranges to catch the few factors that may have been missed due to hardware error. A couple of years ago I did a stats analysis and found some ranges that had fewer factors than expected and these were subsequently refactored.

Thanks for responding.

Just the other day tiny factors were found <1M.

I believe that George said something along the lines "there may be missed factors in the <1M range", but that was long ago.

New question:

Assuming one wanted to spend time looking for missed factors, where would you (or someone else) suggest looking?

For instance; the state of GIMPS at the time of relevant software changes could (I speculate) set limits for ranges of interest.

According to PrimeNet, these are the 58bit and smaller factors found this year. Sorted by factor size. The largest exponents are near 9.03M.

Code:

99023    980560602097
1016959    18653763679711
1000249    18718209673951
1012631    19848410108993
1010083    20476992464473
1019177    21488556163649
1006037    23404082594681
1019747    23799508124081
1018313    24324727758641
1008979    31637343728201
1012087    32573220546271
1013879    34625346725441
1015499    35394567725641
1015507    37283510851289
1001023    43400827672903
864007    46477709992471
1009997    48129370881049
1002289    48903508485137
1012631    50384038680457
1015549    51839698005217
1017703    61295136287513
1018207    61634570426393
1009991    65613588599249
1012751    66624391675561
1019617    73345567713311
1001549    78737816245961
1000907    80089865682031
1005913    82565258566961
1011817    85194319553513
1002191    89413003603849
1002851    90306098748169
1011733    103881086013473
1001023    105325934316809
1002809    108624581750791
1017781    119335489914337
1004657    120969487520809
1005593    121804213923937
400157    128240538662921
1011797    151518203436449
1007651    185960105727329
1002191    206961669674729
1007723    207476662211801
106243    220091409617207
1016159    227720112092783
1014199    228600194965057
1010957    242816965849993
1003913    252300058074929
1015127    259085723606873
1015471    263462537414369
1002851    265430938262447
100523    265722819270463
1002359    298610005183879
1017437    317388210528121
2420779    319464569056489
1001381    348075947962759
1005493    351900700637111
1004743    355675043217721
1006513    360597218428999
1006507    368083732552673
1011671    372929571475063
4133449    402229658827897
1010201    406245525415663
104681    421630521561673
4342111    431267678479543
4247863    446251303961191
1018109    471922881727343
1008857    504298736777233
1014193    518205426514553
1016303    539032923610121
4274969    554148465384329
1010579    561804491415863
1009457    569495154117559
1008613    570848425426423
1017131    583226334994423
108869    640334321542471
1004441    649241734499201
1018559    720553676854457
1014833    724291410620993
108401    754055767693049
1010809    808866600136687
1009837    907916064221279
1018313    984707807470577
83009    990980413706951
125399    1011662939203313
1003943    1134859295559161
1007179    1166357726794913
1018291    1200214155372671
1004371    1201615242506641
1007959    1206562695464911
1012771    1225524778255703
1002359    1346039738821537
1002173    1357535167633721
99079    1412184542980087
1002511    1475685631549127
1002143    1533246771531151
1005493    1538728354360943
1008913    1601754304362871
1011431    1783738457388967
1005527    1797217598520353
1004233    1806811609034063
1012993    1895467579412423
1012087    1936194720326063
901097    1952850613315457
98009    1988617268030023
1006193    2020846479258359
1017011    2033149477786793
901547    2124272174277161
400217    2394731204476207
1009601    2400592635533327
1014193    2447466101263849
1009637    2490076365496351
1004567    2507583067761001
1013923    2725924871816233
1002149    2803832954121263
1002569    2872444793803049
62099    3019058178003401
82307    3030500283220913
1004779    3033896470116761
1018313    3227638113018551
1010353    3236064988674431
1008809    3267646386769361
101273    3271387127383937
86857    3321995396388511
1017827    3435506187107663
1009991    3528760434779887
104513    3611892180968927
1014131    3652586416418783
100271    3661741939738607
83137    3671207650081553
1001639    3860527691238961
1004441    3899769535437313
9028337    3912521837704031
1016573    3940972432466063
1014199    4020853779326623
104827    4312079700970529
1000253    4365256714603753
1016947    4508448594046097
90821    4530157350487799
104123    4848782238266807
1001659    5095495810541057
103471    5188727978053273
85487    5316775202138161
1011779    5366906234880833
1016051    5367413221442759
1008809    5434110214311407
93719    5449249011160751
1001947    6023437950357383
1015697    6106280787650177
1001023    6239409282646471
1000507    6545453841447847
1009289    6722020453106921
1012997    6828461100959191
1019747    6860676621234559
1013671    7463026192839703
81373    7535738901877169
106087    7545325068873769
107867    8659739619596137
1009037    8710630331154617
82217    8785578980234401
1004873    8920225963481009
1019443    9048286923381911
400009    9326149030431929
1000537    9362759471355617
9028337    9720574988871041
1007459    9974630715927529
126047    10068069852964433
108343    10093628875392599
1007129    10374999104164153
1016959    10468076425908791
1016573    10489367636012537
1011071    10822284427910209
100447    10833463432273607
1008223    11020294552348481
1006339    11206106968395847
1008437    11260060308181127
88523    11278949304402127
1002523    11974269164369623
62131    12184261955089673
1013671    12587896925293649
1017857    12746205441772921
1000907    13671464359549247
60337    14157609727264231
1019209    14199609416529217
88811    15410174172800081
1012703    16826761459540961
127289    16990947052876033
1016053    19055636858196751
1018999    21187947967344409
1009559    21268826671484057
1003193    22446770078845153
1009937    23845373163654071
1182953    24042946210458353
1011677    24410729824112999
1008407    24643610973806777
1001173    25906499624318393
1002517    26137376131629977
1014743    26859693834111353
1018859    27509358587002399
1007813    27948761631467279
1001809    28253697237572929
125119    28706030530418713
1011343    29010047325596663
1620989    29166507389557009
104779    29952897673599311
1005541    30164687516194657
81131    30970934344553807
1005269    31730846049890033
100823    32718508623684503
107903    33240811694356087
66601    33598299665978119
1019267    36035719707737639
125899    37896766522865713
1003621    40858310866986911
105211    41527813489337039
885977    42768654755388593
73693    42798053430500713
1452457    44223530791070777
1011343    45702720956876761
1003363    46374008358700271
1000847    49805097491188079
1618241    51329980060216993
65357    58130304979246361
53609    60792876838136119
104231    61584794440146511
108421    63388824385479511
66221    63396230446135231
102077    63736696785276377
72341    65355437734517401
103511    65928873019240271
1006063    66167532034560599
1009037    66852840610376657
1012829    68232868550629439
1001587    68509862263995583
127219    69961396774604807
1011733    71859146656358623
109589    73530089455028033
77137    74027323761489881
1510799    78128410571491879
1017703    78831282269233657
1001327    79724596802652383
1015871    80239306685666977
1002247    81754558937865607
1000099    82815026005984871
1008863    82866332946794017
1016359    83239897060454089
98887    83256236543665489
73939    83757780760254191
1019357    86371091158126561
63521    86927908707753073
87641    89472672952096751
1010957    95992770210964313
1502689    101582513471959879
1007933    103015778813126183
1006063    104477544626947361
1501663    105064962893473657
82307    109585211839872919
1013791    110528245389881287
1012457    113619522018953569
127301    116783194462665937
72211    122869954525849481
69991    124990441490405599
97771    125898247734526409
1012399    126045865312962607
1004233    128658770240793503
1006193    138559778438573321
1001387    146249244431956031
1013581    148741927534567273
39239    151688561135612231
9000683    152951220467377351
60383    154821431322412159
103177    167230673565034081
41887    168666943367160473
101467    171665469954516919
84067    172890589120324177
66629    177840727690088273
104681    183610827669992551
106367    192625801807206121
101467    195715582128306503
109639    196708855126048247
83843    198423011702650313
108343    216924007232406889
71471    230415693584014439
38833    273437273838431047
107137    278540511429188759

garo · 2010-11-15, 11:48

A Mersenne number has a factor of size x bits with a probability 1/x. Use this to estimate the average number of factors a range should have. Then identify ranges that have too few factors. You could use 2 SD as a starting point. The resulting ranges are where I would start looking. There is an old thread here that will help you: http://www.mersenneforum.org/showthread.php?t=1425

alpertron · 2010-11-15, 12:59

Quote:

Originally Posted by lorgix

According to PrimeNet, these are the 58bit and smaller factors found this year. Sorted by factor size. The largest exponents are near 9.03M.

A lot of these factors (if not all) are not the first prime factors found for that exponent. If a prime factor is found, GIMPS does not try to continue factoring that Mersenne number.

markr · 2010-11-15, 13:49

Quote:

Originally Posted by alpertron

A lot of these factors (if not all) are not the first prime factors found for that exponent. If a prime factor is found, GIMPS does not try to continue factoring that Mersenne number.

Indeed, prior to version 5 of the server, about three years ago, GIMPS only kept one factor for each exponent in its database. (Of course other folk tried to keep track of all factors.)

lorgix · 2010-11-15, 15:53

Quote:

Originally Posted by garo

A Mersenne number has a factor of size x bits with a probability 1/x. Use this to estimate the average number of factors a range should have. Then identify ranges that have too few factors. You could use 2 SD as a starting point. The resulting ranges are where I would start looking. There is an old thread here that will help you: http://www.mersenneforum.org/showthread.php?t=1425

I wouldn't have guessed it was that simple. I've had some success finding factors using other statistical methods though.
I integrate over a given exponent range and bit depth, and then compare the results to the distribution of known factors, right?

Some of the ranges mentioned in the thread has actually caught my attention already, by other means.

I'm under the impression that truly missed factors 58bit or smaller are rare at this point. (59-60; I have little basis to speculate) I will probably give this some more attention. Thanks for the pointers.

Quote:

Originally Posted by alpertron

A lot of these factors (if not all) are not the first prime factors found for that exponent. If a prime factor is found, GIMPS does not try to continue factoring that Mersenne number.

I am aware (I just realized the first factor is composite btw). I haven't checked the list with regard to that, it's a simple result query.

Would this be an interesting example?;

1012631,243031441,
1012631,647776000177,2008-07-16 09:30
1012631,19848410108993,2010-11-02 23:32
1012631,50384038680457,2010-11-02 23:32

Quote:

Originally Posted by markr

Indeed, prior to version 5 of the server, about three years ago, GIMPS only kept one factor for each exponent in its database. (Of course other folk tried to keep track of all factors.)

I did not think of that, although it sounds familiar. Might have read it in some older documentation.

Now, how does FactorOverride work? Could someone please tell me where to look for an accurate description of how it currently behaves? Or just give a brief description?

cheesehead · 2010-11-15, 20:59

Quote:

Originally Posted by lorgix

Now, how does FactorOverride work?

All it does is override the default bit limit for TF. It changes nothing else (such as the algorithm).

Prime95 source module commonc.h specifies the default TF bit limits. In v25, they're:

Code:

/* These breakeven points we're calculated on a 2.0 GHz P4 Northwood: */

#define FAC80    516000000L
#define FAC79    420400000L
#define FAC78    337400000L
#define FAC77    264600000L
#define FAC76    227300000L
#define FAC75    186400000L
#define FAC74    147500000L
#define FAC73    115300000L
#define FAC72    96830000L
#define FAC71    75670000L
#define FAC70    58520000L
#define FAC69    47450000L
#define FAC68    37800000L
#define FAC67    29690000L
#define FAC66    23390000L

/* These breakevens we're calculated a long time ago on unknown hardware: */

#define FAC65    13380000L
#define FAC64    8250000L
#define FAC63    6515000L
#define FAC62    5160000L
#define FAC61    3960000L
#define FAC60    2950000L
#define FAC59    2360000L
#define FAC58    1930000L
#define FAC57    1480000L
#define FAC56    1000000L

Interpretation: FACnn is the low end of the range of exponents for which nn is the default TF limit. That range extends up to FAC(nn+1).

For example, exponents between 47,450,000 and 58,520,000 have a TF bit limit of 69 by default. Unless FactorOverride is used, Prime95 will TF up through 2^69 for exponents in that range.

Exponents greater than 516,000,000 all have a default TF limit of 80 at present, but future versions of Prime95 might specify ranges for limits of 81, 82 ...

Now, if you look at the bit levels to which exponents have actually been TFed, you'll find that there's no break at 6515000. Exponents between 6000000 and 6515000 have all been TFed to 63 (or more), as well as exponents 6515000-6999999. That's because the TF default limits used to be different in earlier versions of Prime95. At the time when exponents between 6000000 and 6515000 were being TFed, the then-current version of Prime95 specified a lower exponent range for TF-to-63 than it does now. I.e., FAC63 (and most other FACnn) then had a lower value than it does now.

Note: FactorOverride can be used to set either a higher or a lower TF limit than the default value.

markr · 2010-11-16, 04:09

Quote:

Originally Posted by lorgix

I wouldn't have guessed it was that simple.

As you've probably guessed, it's an approximation.

Quote:

Originally Posted by lorgix

Would this be an interesting example?;

1012631,243031441,
1012631,647776000177,2008-07-16 09:30
1012631,19848410108993,2010-11-02 23:32
1012631,50384038680457,2010-11-02 23:32

The first one, without a date, would have been from PrimeNet v4; the rest from v5. It's an example of how things are supposed to be, with factors found in order of size.

Quote:

Originally Posted by lorgix

Now, how does FactorOverride work? Could someone please tell me where to look for an accurate description of how it currently behaves? Or just give a brief description?

Perhaps you also read about FactorOverride in some older documentation. It was dropped starting with client versions 25.x.

Currently, trial-factoring worktodo lines specify the starting & ending level. Previously, up to client version 24.x, they looked like "Factor=21990487,65", with the starting level only and the client determined the ending level. FactorOverride could be used to change the ending level. It did not work with PrimeNet communication turned on. You would have to find an undoc.txt from v24.x or earlier for a definitive write-up.

cheesehead · 2010-11-16, 04:45

Quote:

Originally Posted by markr

It was dropped starting with client versions 25.x.

That's what I get for staying a version behind. When will I learn?

Please consider all verb tenses in post #94 to be adjusted accordingly.

henryzz · 2010-11-16, 16:33

Quote:

Originally Posted by cheesehead

That's what I get for staying a version behind. When will I learn?

Please consider all verb tenses in post #94 to be adjusted accordingly.

two versions behind
26.x is out

cheesehead · 2010-11-17, 07:59

Quote:

Originally Posted by henryzz

two versions behind
26.x is out

One version behind. I'm using v25.8

lorgix · 2011-01-10, 15:42

I've started using a very handy tool for simplifying batch factorization.

Converting PrimeNet queries that can then be copy-pasted into worktodo.txt.

http://mersenne-aries.sili.net/pfactor.php

The older probability calculator has some new features too:

http://mersenne-aries.sili.net/prob.php

Thank you James Heinrich!

2010-11-15, 11:48	#90
garo Aug 2002 Termonfeckin, IE 2⁴·173 Posts	A Mersenne number has a factor of size x bits with a probability 1/x. Use this to estimate the average number of factors a range should have. Then identify ranges that have too few factors. You could use 2 SD as a starting point. The resulting ranges are where I would start looking. There is an old thread here that will help you: http://www.mersenneforum.org/showthread.php?t=1425

2011-01-10, 15:42	#99
lorgix Sep 2010 Scandinavia 3·5·41 Posts	I've started using a very handy tool for simplifying batch factorization. Converting PrimeNet queries that can then be copy-pasted into worktodo.txt. http://mersenne-aries.sili.net/pfactor.php The older probability calculator has some new features too: http://mersenne-aries.sili.net/prob.php Thank you James Heinrich!