View Single Post
Old 2010-10-16, 18:34   #23
lorgix's Avatar
Sep 2010

3·5·41 Posts

Originally Posted by Mini-Geek View Post
These "k=2" you are talking about are really k=1. Factors are of the form 2kp+1. In other words, they're mp+1, with m always even. With these factors, m=2 and k=1, since the factor is equal to 2*p+1.
I'd bet that the factors of the k's break down, on average, like the factors of any natural number of about their size. And that the chance of any given k producing a factor is related to the equation given at "(how_far_factored-1) / (exponent times Euler's constant (0.577...))".
I don't know what that means precisely as far as how many k's will be smooth to such-and-such bounds, but the GIMPS Math page says "The chance of finding a factor and the factoring cost both vary with different B1 and B2 values. Dickman's function (see Knuth's Art of Computer Programming Vol. 2) is used to determine the probability of finding a factor, that is k is B1-smooth or B1-smooth with just one factor between B1 and B2. The program tries many values of B1 and if there is sufficient available memory several values of B2, selecting the B1 and B2 values that maximize the formula above."

I'll admit to this embarrassing mistake. 1=/=2

Next you are touching on some very interesting stuff. Some people might remember me and at least one other person on this forum asking about the precise algorithm for determining optimal bounds given certain conditions.

I have no reason to doubt that they break down essentially the same way, but it would be nice to see it, or have proof.

I should follow up on those references, and hope I know enough math to wrap my head around it. I love natural constants btw; memorized Pi to 1k decimal places... For Euler's I only know ~0.577215664901... which happens to be close to 3^-0.5.
lorgix is offline   Reply With Quote