mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-04-28, 19:51   #1
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2·5·37 Posts
Default Probability of finding a factor in TF

Alrighty,

At http://www.mersenne.org/math.htm, we are told:
Quote:
the chance of finding a factor between 2^x and 2^x+1 is about 1/x.
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 is offline   Reply With Quote
Old 2003-04-29, 15:07   #2
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2×5×37 Posts
Default

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]
eepiccolo is offline   Reply With Quote
Old 2003-04-29, 19:47   #3
S80780
 
Jan 2003
far from M40

53 Posts
Default

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
S80780 is offline   Reply With Quote
Old 2003-05-09, 02:53   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default Re: Probability of finding a factor in TF

Quote:
Originally Posted by eepiccolo
At http://www.mersenne.org/math.htm, we are told:
Quote:
the chance of finding a factor between 2^x and 2^x+1 is about 1/x.
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?
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.
cheesehead is offline   Reply With Quote
Old 2003-06-07, 05:56   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

For a thorough earlier discussion, see the thread "Does the LL test:s factorization save or waste CPU time?" in The Software forum at http://www.mersenneforum.org/viewtopic.php?t=78, especially svempasnake's table comparing the 1/n prediction to the actual number of factors found, on page 3 at Mon Sep 16, 2002 9:32 pm (http://www.mersenneforum.org/viewtop...highlight=#895).
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Probability of factor (TF) nuggetprime Math 2 2011-03-19 22:14
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
probability of finding a Mersenne prime optim Math 2 2003-12-06 19:03
Probability of finding a factor in DC p-1 Deamiter Math 4 2002-12-25 06:06
Probability of finding a prime number Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 12:16.

Sat Sep 26 12:16:31 UTC 2020 up 16 days, 9:27, 1 user, load averages: 1.66, 1.54, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.