mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Probability of finding a factor in TF (https://www.mersenneforum.org/showthread.php?t=549)

 eepiccolo 2003-04-28 19:51

Probability of finding a factor in TF

Alrighty,

At [url]http://www.mersenne.org/math.htm[/url], we are told:
[quote]the chance of finding a factor between 2^x and 2^x+1 is about 1/x.[/quote]
My question is this: is this probability dependent or independent of whether or not other factors have been found? And for what values of x is this valid? It doesn't seem like it shouild work for small values of x.

Tim

 eepiccolo 2003-04-29 15:07

In a posibly related note, is the following infinite series equal to 1?
[code:1]inf
Σ 1/(n(n+1)) = 1 ?
n=1[/code:1]

 S80780 2003-04-29 19:47

Yes, it is.

1/(n*(n+1))
= (n+1-n)/(n*(n+1))
= (n + 1)/(n*(n+1)) -n/(n*(n+1))
= 1/n - 1/(n+1)

So, the kth partial - sum has the value

1 - 1/(k+1)

which's limit for k to infinity is 1 q.e.d.

Sums like these, where a summand is (partly) nihilized by its successor are called telescope sums.

Benjamin

Re: Probability of finding a factor in TF

[quote="eepiccolo"]At [url]http://www.mersenne.org/math.htm[/url], we are told:
[quote]the chance of finding a factor between 2^x and 2^x+1 is about 1/x.[/quote][/quote]

First, let's note that the sentence begins with "Looking at past factoring data we see that the chance ..." Right now I don't recall whether I've seen a proof of that estimate. Judging by the sentence's wording, it may be an empirical observation.

[quote]My question is this: is this probability dependent or independent of whether or not other factors have been found?[/quote]

If I understand correctly, what is meant is "... the chance that 2^p-1 has a factor between 2^x and 2^(x+1) is approximately 1/x."

That is, it refers to the probability of the existence of a factor (known or unknown) of 2^p-1 within the specified range, not necessarily the probability of discovering a previously-unknown factor there after some factors of 2^p-1 are already known.