Run P-1 before PRP tests

[VictordeHolland]

Originally Posted by petrw1

When I try the "show source" link I get:

Fatal error: Call to undefined function htmlentities_safe() in /var/www/vhosts/mersenne.ca/httpdocs/prob.php on line 15

The calculator uses more or less the same code as Prime95:

function FactorProbability($exponent, $B1, $B2, $HowFarFactoredBits=false) {
    // adapted from guess_pminus1_bounds() in ecm.c in Prime95 source

    if ($B1 < 30) {
        return 0;
    }
    $B2 = max($B2, $B1);
    if (!$HowFarFactoredBits) {
        //$HowFarFactoredBits = FactorBits($exponent);
        $HowFarFactoredBits = FactorBits($exponent) - 1; // last level of TF is now done *after* P-1 by default
    }
    $ProbabilityThreshold = 0.0001;

    $log2 = log(2);
    $logB1 = log($B1);
    $logB2 = log($B2);

    $k =  1; /* K in K*B^N+C. Must be a positive integer. */
    $b =  2; /* B in K*B^N+C. Must be two. */
    $c = -1; /* C in K*B^N+C. */

    $kk = 1.5 * pow(2.0, $HowFarFactoredBits);
    if (($k == 1.0) && ($b == 2) && ($c == -1)) {
        $kk = $kk / 2.0 / $exponent;
    }
    $LogKK = log($kk);

    $temp = $kk / (($B1 + $B2) / 2);
    $LogTemp = log($temp);

    $FactorProbability = 0;
    $H = $HowFarFactoredBits;

    while (true) {

/* If $temp < 1.0, then there are no factor to find in this bit level */
        if ($LogTemp > 0) {

/* See how many smooth k's we should find using B1 */
/* Using Dickman's function (see Knuth pg 382-383) we want k^a <= B1 */
            $Prob1 = DickmansFunction($logB1 / $LogKK);

/* See how many smooth k's we should find using B2 */
/* Adjust this slightly to eliminate k's that have two primes > B1 and < B2 */
/* Do this by assuming the largest factor is the average of B1 and B2 */
/* and the remaining cofactor is B1 smooth */
            $Prob2 = $Prob1 + ((DickmansFunction($logB2 / $LogKK) -  $Prob1) * (DickmansFunction($logB1 / $LogTemp) / DickmansFunction($logB2  / $LogTemp)));

            if ($Prob2 < $ProbabilityThreshold) {
                break;
            }

/* Add this data in to the total chance of finding a factor */
            $FactorProbability += $Prob2 / ($H + 0.5);
        }
        $H++;
        $LogKK   += $log2;
        $LogTemp += $log2;
    }
    return $FactorProbability;
}

[Dubslow]

Originally Posted by VictordeHolland

The calculator uses more or less the same code as Prime95:

What language is that?

[ATH]

Originally Posted by GP2

I did this with UsePrimenet=0 and submitted the results manually. You get no Primenet credit (unless you found a factor), but it does add a line to the History section.

It claimed that I got credit when I submitted the P-1 line even with no factor. I did not check if my P-1 credit was raised by that amount, but I will check next time.

[Mark Rose]

Originally Posted by Dubslow

What language is that?

The Black Speech of Mordor.

[VictordeHolland]

Originally Posted by Mark Rose

The Black Speech of Mordor.

James's site is mainly serving pages created from a database, so PHP makes a lot of sense. What is wrong with using PHP for this case?

// adapted from guess_pminus1_bounds() in ecm.c in Prime95 source

This is from ecm.c that it is referring to:

/* Determine the probability of P-1 finding a factor */
/* This code was pulled from guess_pminus1_bounds */

double guess_pminus1_probability (
    struct work_unit *w)
{
    double    log2, logB1, logB2, h, kk, logkk, temp, logtemp, prob;

/* Constants */

    log2 = log ((double) 2.0);
    logB1 = log (w->B1);
    logB2 = log (w->B2);

/* What is the "average" value that must be smooth for P-1 to succeed? */
/* Ordinarily this is 1.5 * 2^how_far_factored.  However, for Mersenne */
/* numbers the factor must be of the form 2kp+1.  Consequently, the */
/* value that must be smooth (k) is much smaller. */

    kk = 1.5 * pow (2.0, w->sieve_depth);
    if (w->k == 1.0 && w->b == 2 && w->c == -1) kk = kk / 2.0 / w->n;
    logkk = log (kk);

/* Set temp to the number that will need B1 smooth if k has an */
/* average-sized factor found in stage 2 */

    temp = kk / ((w->B1 + w->B2) / 2);
    logtemp = log (temp);

/* Loop over increasing bit lengths for the factor */

    prob = 0.0;
    for (h = w->sieve_depth; ; ) {
        double    prob1, prob2;

/* If kk < 1.0, then there are no factors to find in this bit level */

        if (logkk > 0.0) {

/* See how many smooth k's we should find using B1 */
/* Using Dickman's function (see Knuth pg 382-383) we want k^a <= B1 */

            prob1 = F (logB1 / logkk);

/* See how many smooth k's we should find using B2 (if temp < 1.0 then we should find them all) */
/* Adjust this slightly to eliminate k's that have two primes > B1 and < B2 */
/* Do this by assuming the largest factor is the average of B1 and B2 */
/* and the remaining cofactor is B1 smooth */

            if (logtemp <= 0.0) prob2 = 1.0;
            else prob2 = prob1 + (F (logB2 / logkk) - prob1) *
                         (F (logB1 / logtemp) / F (logB2 / logtemp));
            if (prob2 < 0.0001) break;

/* Add this data in to the total chance of finding a factor */

            prob += (1.0 - prob) * prob2 / (h + 0.5);
        }

/* Move to next bit level */

        h += 1.0;
        logkk += log2;
        logtemp += log2;
    }

/* Return the final probability */

    return (prob);
}

[alpertron]

Originally Posted by petrw1

I accept the fact that you know WAYYY more about P-1 than I do so feel free to elaborate on the following as you see fit.

What I have done is created a table with various B1/B2 bounds (yours is first) for P-1 in the range you suggest.
This specific table uses Exponent 2,600,001.
I'll explain the columns:

B1/B2: various choices for B1 and B2 bound for the new P-1
Pct: The odds of it finding a factor strictly based on this: http://www.mersenne.ca/prob.php
GD: The GhzDays to do the P-1 based on the same URL above.
-- Then 4 pairs of columns as follows (Most Exponents in the 2.6M range have existing P-1 runs with an estimated success rate of about 3.25% - 4%):
3.25: The number at the top of the pair of columns is the odds of the existing P-1 run finding a factor.
PerFac: The calculated number of P-1 with the new bounds required to find a factor taking into account the odds from the prior P-1 run
GD/F: The calculated GhzDays required to find a new factor based on the above parms. I suggest we want to minimize this number.

For example: From the first row: Statistically, 68.97 P-1 runs would be required to find a factor based on the net Percent of 4.70 - 3.25 (New - Existing P-1). Then based on 0.13 GhzDays per new P-1 it would take 8.97 total GhzDays of P-1 work to find the new factor.

NOTE: What this table does NOT take into account is the ECM work already done on these Exponents. More than I could bite off.

					3.25		3.50		3.75		4.00	
B1	B2	         Pct	GD	PerFac	GD/F	PerFac	GD/F	PerFac	GD/F	PerFac	GD/F
500000	15000000	4.70	0.13	68.97	8.97	83.33	10.83	105.26	13.68	142.86	18.57
1000000	20000000	5.45	0.21	45.45	9.32	51.28	10.51	58.82	12.06	68.97	14.14
2000000	40000000	6.62	0.42	29.67	12.46	32.05	13.46	34.84	14.63	38.17	16.03
2600000	52000000	7.08	0.53	26.11	13.84	27.93	14.80	30.03	15.92	32.47	17.21
2600000	26000000	6.32	0.39	32.57	12.70	35.46	13.83	38.91	15.18	43.10	16.81
3000000	60000000	7.34	0.61	24.45	15.01	26.04	15.99	27.86	17.10	29.94	18.38
4000000	80000000	7.86	0.82	21.69	17.77	22.94	18.78	24.33	19.93	25.91	21.22
5200000	104000000	8.33	1.06	19.69	20.87	20.70	21.95	21.83	23.14	23.09	24.48

I reserved all exponents with known factors from 2300000 to 2310000 for ECM, but I changed them in my computer to perform P-1 with bounds B1=500000, B2=15M instead.

Up to this moment, Prime95 ran up to 2300300 (13 numbers) and it found three new factors, for exponents 2300017, 2300057 and 2300153. If it is true that I can find factors only 1 of every 68 numbers, that means that I'm very lucky.

[VictordeHolland]

If anybody wants my P95 P-1 savefiles (B=10e6, B2=200e6) from exponents in the range 1.5M-1.7M (on 2500+ exponents without factors) to extend them for instance, let me know.

Note that the exponents in question also have had 280 ECM curves @B1=50,000 done since the P-1 runs. Somebody better educated in the subject can probably calculate if it still is useful to run more P-1 or just ECM.

[kladner]

Originally Posted by Mark Rose

The Black Speech of Mordor.

The Black Speech of Mordor:

Ash nazg durbatulûk, ash nazg gimbatul,
Ash nazg thrakatulûk agh burzum-ishi krimpatul.

Translated, the words mean:

One ring to rule them all, one ring to find them,
One ring to bring them all and in the darkness bind them.

When Gandalf recited the inscription in Black Speech at the Council of Elrond, everyone trembled:

The change in the wizard's voice was astounding. Suddenly it became menacing, powerful, harsh as stone. A shadow seemed to pass over the high sun, and the porch for a moment grew dark. All trembled, and the Elves stopped their ears.

[alpertron]

Originally Posted by alpertron

I reserved all exponents with known factors from 2300000 to 2310000 for ECM, but I changed them in my computer to perform P-1 with bounds B1=500000, B2=15M instead.

Up to this moment, Prime95 ran up to 2300300 (13 numbers) and it found three new factors, for exponents 2300017, 2300057 and 2300153. If it is true that I can find factors only 1 of every 68 numbers, that means that I'm very lucky.

The computer processed 42 numbers and it found more factors for Mersenne numbers with exponents 2300563, 2300731, 2300999 and 2301199. It is clear that something in the formulas related to the probability of finding factors using P-1 algorithm is wrong.

[axn]

Originally Posted by alpertron

The computer processed 42 numbers and it found more factors for Mersenne numbers with exponents 2300563, 2300731, 2300999 and 2301199. It is clear that something in the formulas related to the probability of finding factors using P-1 algorithm is wrong.

http://www.mersenne.ca/prob.php?expo...tton=Calculate says 5.68%. For 42 tests, that amounts to 2.5 factors. You found 7. Sure that's a lot more, but not impossibly so. The problem is low sample size. Maybe once you've run it for about 1000 exponents, we can have some degree of confidence on the numbers.

[alpertron]

Originally Posted by axn

http://www.mersenne.ca/prob.php?expo...tton=Calculate says 5.68%. For 42 tests, that amounts to 2.5 factors. You found 7. Sure that's a lot more, but not impossibly so. The problem is low sample size. Maybe once you've run it for about 1000 exponents, we can have some degree of confidence on the numbers.

Continuing with the "stroke of luck", after 6 more numbers, the computer found factors of M2301251 and M2301421.