[QUOTE=alpertron;379739]There is a formula on section 4.5.4 (Factoring into Primes) of Knuth's TAOCP that computes the probability of having the second largest prime factor less than some bound (expressed as log B / log N, B is the bound, N is the composite number).

That can be used here, but it appears that the formula is not easy to compute. For example, we could fix the bound to 10[SUP]30[/SUP] and then for all prime exponents between 1M and 2M, add all probabilities. That sum could be (approximately) the expected number of PRP factors in the mentioned range that we could found in a reasonable amount of time.[/QUOTE]

The formula in the book is:

[tex]G(\beta)\, = \,\int\limits_{0}^{\beta}(G(\frac{t}{1-t})-F(\frac{t}{1-t}))\,\frac{dt}{t}[/tex]

For the values of [tex]\beta[/tex] near zero, the function F can be ignored, as can be seen in the graph in the page following the definition. We can also make t/(1-t) = t as an approximation.

Deriving both members we get:

[tex]G'(t) \approx \frac{G(t)}{t}[/tex]

[tex]\frac{G'(t)}{G(t)} \approx \frac{1}{t}[/tex]

[tex]\log G(t) \approx C + \log(t)[/tex]

[tex]G(t) \approx Kt[/tex]

From the table of values of G(t) in the book, we can assign K = 1.8

I wrote the following program in UBASIC language:

[QUOTE]
10 S=0
20 P=nxtprm(1000000)
30 B=(30*log(10))/(P*log(2))
40 S=S+1.8*B
50 P=nxtprm(P)
60 if P<2000000 then 30
70 print S
[/QUOTE]

The program prints the number 8.78. This is a crude approximation, but it appears that there are several PRPs to be found in the range 1M to 2M in a reasonable amount of time by finding more prime factors.

A more approximate result can be found using the method of undetermined coefficients.

[tex]G'(t)\, = \,G(\frac{t}{1-t})\frac{1}{t}[/tex]

[tex]G(t) = Kt + Lt^2 + O(t^3)[/tex]

[tex]\frac{t}{1-t} = t + t^2 + O(t^3)[/tex]

[tex]K + 2Lt + O(t^2) = (K(t+t^2+O(t^3)) + L(t^2+O(t^3)) + O(t^3))\frac{1}{t}[/tex]

[tex]K + 2Lt + O(t^2) = K + (K+L)t + O(t^2)[/tex]

[tex]L = K[/tex]

[tex]G(t) = 1.8t(1+t) + O(t^3)[/tex]

The result is again 8.78.

Using the formulas above I computed the expected numbers of PRP to be found in different ranges. Notice that most Mersenne numbers are not factored up to these bounds because the factorization stopped when the first prime factor was found.

[CODE]
Range Known PRPs 25 digits 30 digits 35 digits
------------------------------------------------------------
1K-2K 45 14 17 20
2K-5K 26 17 20 24
5K-10K 16 12 14 16
10K-20K 10 11 13 15
20K-50K 8 13 16 18
50K-100K 7 9 11 13
100K-200K 5 9 10 12
200K-500K 5 11 13 15
500K-1M 3 8 9 11
1M-2M 3 7 9 10
2M-3M 0 4 5 6
3M-4M 0 3 3 4
4M-5M 0 2 3 3
5M-10M 0 7 8 9
[/CODE]

[QUOTE=alpertron;379793]The formula in the book is:

[tex]G(\beta)\, = \,\int\limits_{0}^{\beta}(G(\frac{t}{1-t})-F(\frac{t}{1-t}))\,\frac{dt}{t}[/tex]

For the values of [tex]\beta[/tex] near zero, the function F can be ignored, as can be seen in the graph in the page following the definition. We can also make t/(1-t) = t as an approximation.

Deriving both members we get:

[tex]G'(t) \approx \frac{G(t)}{t}[/tex]

[tex]\frac{G'(t)}{G(t)} \approx \frac{1}{t}[/tex]

[tex]\log G(t) \approx C + \log(t)[/tex]

[tex]G(t) \approx Kt[/tex]
[/QUOTE]

This ignores C. exp(C) might be quite large. We don't know the value of C.

[QUOTE=alpertron;379805]A more approximate result can be found using the method of undetermined coefficients.

[tex]G'(t)\, = \,G(\frac{t}{1-t})\frac{1}{t}[/tex]

[tex]G(t) = Kt + Lt^2 + O(t^3)[/tex]

[tex]\frac{t}{1-t} = t + t^2 + O(t^3)[/tex]

[tex]K + 2Lt + O(t^2) = (K(t+t^2+O(t^3)) + L(t^2+O(t^3)) + O(t^3))\frac{1}{t}[/tex]

[tex]K + 2Lt + O(t^2) = K + (K+L)t + O(t^2)[/tex]

[tex]L = K[/tex]

[tex]G(t) = 1.8t(1+t) + O(t^3)[/tex]

The result is again 8.78.[/QUOTE]

We do not know that the implied constant in the O() estimate is small.
Without knowing what the constant is, any numerical estimate is just a
SWAG.

[QUOTE=R.D. Silverman;379832]This ignores C. exp(C) might be quite large. We don't know the value of C.[/QUOTE]
I found the value of K = exp(C) from the table of values of G(b) as I wrote several posts above.

[QUOTE]We do not know that the implied constant in the O() estimate is small.
Without knowing what the constant is, any numerical estimate is just a
SWAG.[/QUOTE]
The value of t in these cases is less than 0.0001, so I think that O(t^3) should be small as well. As I stated in a previous post, the result was the same when using the quadratic coefficient or not. When using the quadratic coefficient, the values are exact to three significant digits for t<0.1 as can be seen on the table of values of G(t) in the book. All calculations for the table include both the linear and quadratic coefficient.

[QUOTE=alpertron;379835]I found the value of K = exp(C) from the table of values of G(b) as I wrote several posts above.


The value of t in these cases is less than 0.0001, so I think that O(t^3) should be small as well. As I stated in a previous post, the result was the same when using the quadratic coefficient or not. When using the quadratic coefficient, the values are exact to three significant digits for t<0.1 as can be seen on the table of values of G(t) in the book. All calculations for the table include both the linear and quadratic coefficient.[/QUOTE]

It looks good. But I hesitate to draw any conclusions with B this small,
relative to the size of the original composite(s). R. Guy's "Law of Small
Numbers" kicks in.

Your work gives reasonable estimates, but we don't know if they apply
for factors this small relative to the original composite.

Well, I said that this is an approximation. Before these calculations, I had no idea of how many PRPs we would find.

[QUOTE=Gordon;379856]So how many Mersenne Primes was that you found again ???

Please reply with the prime exponent you found and we'll throw you a :party:[/QUOTE]
Well, this is not correct. In order to find these Mersenne primes, you need several people: the inventor of the algorithm, one or more persons that polish it making more amenable to computers, the one who code it in an optimized way, and the person who runs the computer that finally finds the results.

So you are just one little line in the "cast of characters" (that spans several screens) of the discovery of M2976221.

Silverman is in the second category of people mentioned above, but I think he is not related to anything related to Mersenne number primality.

[STRIKE]The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]eponymous thread[/URL].[/STRIKE]

The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]thread for posts that are less than useful[/URL].

[QUOTE=alpertron;379857]
Silverman is in the second category of people mentioned above, but I think he is not related to anything related to Mersenne number primality.[/QUOTE]

Wrong again. Check with David Slowinski.

A long time prior to GIMPS (early 80's), I provided David with a
moderately large list of exponents that did not need to be factored because I
had found small divisors.