[QUOTE=Aramis Wyler;337417]Expected LL work saved TFing 1 expo from 71 to 75 is 1/72+1/73+1/74+1/75 = .054[/QUOTE]This is a mistake which is extremely easy to make, and sorting it out is highly instructive.

Your sum is not giving the probability of anything. It is giving the "expected" number of factors. Extending the sum up to 1/N, we can integrate 1/x from 71 to N and estimate the sum as ln (N/71). If N > 71e, the sum is >1.
We can use the Poisson distribution to get the probabilities of no factors, precisely one factor and one or more factors from the expected number E:

P(x) = E[SUP]x[/SUP]*e[SUP]-E[/SUP]/x!
Note that the sum from x=0 to infinity is 1.

P(0) = e[SUP]-E[/SUP]
P(1) = E*e[SUP]-E[/SUP]
P(>0) = 1 - e[SUP]-E[/SUP]

Now when E<<1, P(1) and P(>0) --> E.
This makes estimating things very easy. So easy that many fall into the trap you did. Note that
1 - e[SUP]-E[/SUP] = .054 - .0015....
so the error in this case is neither very obvious nor serious.


David

In the case where I'm doing trial factoring, and I think in general everyone in the gpu to 72 group whose sub-forum we are posting in, numbers with factors are not factored.

In an objective sense, what I said (Expected LL work saved TFing 1 expo from 71 to 75 is 1/72+1/73+1/74+1/75 = .054) is certainly wrong. But when you consider our context as declared in my first paragraph above, these variables are not independant: 1 and only 1 can occur, and there can be no factors below bitdepth 72.
[quote=R.D. Silverman] When is it legitimate to add the probabilities? [quote=davieddy] When you want the probability of one of a number of mutually exclusive possible outcomes occurring[/quote][/quote]

David is correct in his response to R.D. Silverman above, though goes off a bit after that by somehow assuming these events are independent, or that it's even possible for events to be both independant AND mutually exclusive.

[quote=davieddy]1 - e-E = .054 - .0015...[/quote]
Subtracting the chance of them overlapping would make sense if they were independant, but they are not. They are mutually exclusive for the purpose of GPUto72 TF work.

Independence of probabilities
 

x and y are primes between 2[SUP]71[/SUP] and 2[SUP]75[/SUP].
Choose a random number N between 2[SUP]60,000,000[/SUP] and 2[SUP]65,000,000[/SUP].
The probability that N is a multiple of x is 1/x.

Suppose x is a factor of N.
Does this affect the probability that N is a multiple of y being 1/y?
If so how and why?

David

Edit: I'll answer this.

The probability of N being a multiple of (xy) is 1/(xy) = (1/x) * (1/y).
The probabitities are independent.

In davieddie's world, where no factoring actually gets done, I suppose it's fair to treat them as independant even if for practical purposes they are mutually exclusive. Home field advantage. :smile:

[QUOTE=Aramis Wyler;337551]In davieddie's world, where no factoring actually gets done, I suppose it's fair to treat them as independant even if for practical purposes they are mutually exclusive. Home field advantage. :smile:[/QUOTE]I didn't realize that Chalsall was altering the factorization of composites at will.
That guy really is the Devil incarnate!

[QUOTE=Aramis Wyler;337551]In davieddie's world, where no factoring actually gets done, I suppose it's fair to treat them as independant even if for practical purposes they are mutually exclusive. Home field advantage. :smile:[/QUOTE]

These guys are theorists... Rarely even worth the carbon.

[QUOTE=Isacc Asimov]The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!' but 'That's funny...'[/QUOTE]

[QUOTE=R.D. Silverman;337492]Clueless.
He ADDED four probabilities. But they were NOT independent![/QUOTE]
As I explained to Aramis, your mistake is very easy to make.
He added four probabilities to obtain the expected number of factors.
They ARE independent, and being <<1, approximate the expected number. Hence the confusion.

To spell it out, expected factors between 2[SUP]71[/SUP] and 2[SUP]75[/SUP] is the integral of 1/(xlnx) = ln(75/71).
Probability of no factors is e[SUP]-ln(75/71)[/SUP] = 71/75

Can you explain why this applies to Mersenne numbers, as well as random ones?

David

[QUOTE=davieddy;337556]Can you explain why this applies to Mersenne numbers, as well as random ones?[/QUOTE]

I don't really know why it is this way and the following text it not a proof, but at least it makes sense to myself:
The chance for a factor between 2[SUP]n-1[/SUP] and 2[SUP]n[/SUP] is 1/n, so the chance for a (roughly) n-bit factor is 1/n, but this is only a (good) estimate.
The product of all prime factors of a number is equal to the number itself.
For a number m there are log[SUB]2[/SUB](m) [I]bitlevels[/I], so summing all products of factor sizes multiplied by the chance for a factor of this size: 1*1/1 + 2*1/2 + 3*1/3 + ... + log[SUB]2[/SUB](m)*1/log[SUB]2[/SUB](m) = 1 + 1 + 1 + ... + 1 = log[SUB]2[/SUB](m)


Oliver

[QUOTE=Aramis Wyler;337417]Expected LL work saved TFing 1 expo from 71 to 75 is 1/72+1/73+1/74+1/75 = .054
Expected LL work saved TFing 2 expos from 71 to 74 is 2*(1/72+1/73+1/74) = .082 (44% more).

I have no real need to be imprecise when [I]I'm sitting in front of a computer.[/I] I thought the difference between 50% (now even more) and 44% was worth clarifying since I was, you know, parked in front of a giant calculator and using it to post on the forum.

I was not arguing though, just clarifying. There are diminishing returns either way.[/QUOTE]
Expected LL work saved TFing 1 expo from 71 to 75 is 1/72 + (1-1/72)*1/73 + (1-(1/72 + (1-1/72)*1/73))*1/74 + (1-(1/72 + (1-1/72)*1/73 + (1-(1/72 + (1-1/72)*1/73))*1/74))*1/75 = 0.053333 not 1/72+1/73+1/74+1/75=0.054434 I think.
Perhaps not surprisingly this simpilfies to 4/75.

Expected LL work saved TFing 1 expo from 71 to 75 is 4/75 = .053333
Expected LL work saved TFing 2 expos from 71 to 74 is 2*(3/74) = 2*0.040540=0.081081

Turns out I missed a few posts. May as well post this anyway now I worked it out.

Probability of no factors between 2[SUP]n-1[/SUP] and 2[SUP]n[/SUP] = (n-1)/n is a special case of the probability of no factors between a[SUP]A[/SUP] and a[SUP]B[/SUP] = A/B
from which it follows immediately that the probability of no factors between 2[SUP]71[/SUP] and 2[SUP]75[/SUP] is 71/75.
(Even more immediately than (71/72)*(72/73)*(73/74)*(74/75) = 71/75:smile:)

Now I gave a derivation of this formula which is so simple and plausible that you feel there must be something in it:

Multiples of a prime p have p-1 integers between them.
If we choose a random number N between 2[SUP]60,000,000[/SUP] and 2[SUP]65,000,000[/SUP], the probability that p is not a factor of N is (1 - 1/p).
From the PNT or Mertens' theorem or otherwise, it is easy to show that the product of (1 - 1/p) for all primes between a[SUP]A[/SUP] and a[SUP]B[/SUP] is A/B.

Now it is very tempting to just say QED, but two big issues rear their heads:
1) Independence: is the probability of p[sub]n[/sub] being a factor still 1/p[sub]n[/sub] even if we know none of p[sub]1[/sub] to p[sub]n-1[/sub] divide N?

2) The form of Mersenne factors

CAN SOMEONE SORT THIS OUT?
BOB?
PLEASE???

David

[QUOTE=davieddy;337690]Probability of no factors between 2[SUP]n-1[/SUP] and 2[SUP]n[/SUP] = (n-1)/n is a special case of the probability of no factors between a[SUP]A[/SUP] and a[SUP]B[/SUP] = A/B
from which it follows immediately that the probability of no factors between 2[SUP]71[/SUP] and 2[SUP]75[/SUP] is 71/75.
(Even more immediately than (71/72)*(72/73)*(73/74)*(74/75) = 71/75:smile:)

Now I gave a derivation of this formula which is so simple and plausible that you feel there must be something in it:

Multiples of a prime p have p-1 integers between them.
If we choose a random number N between 2[SUP]60[/SUP] and 2[SUP]65[/SUP], the probability that p is not a factor of N is (1 - 1/p).
From the PNT or Mertens' theorem or otherwise, it is easy to show that the product of (1 - 1/p) for all primes between a[SUP]A[/SUP] and a[SUP]B[/SUP] is A/B.

Now it is very tempting to just say QED, but two big issues rear their heads:
1) Independence
2) The form of Mersenne factors

CAN SOMEONE SORT THIS OUT?
BOB?
PLEASE???

David[/QUOTE]

I could give it a try:

2) well 2^65-2^60 = 2^60+2^61+2^63+2^64 = 15*2^60
(15*2^60)/(2*p) = (15*2^59)/p there are at most this many candidate factors.

1) though I don't know how many would get thrown from lower candidates being eliminated I know there are likely some depending on p (since 2*k*p+1 has at least one more bit than p, for p=60000000 this gives about 52 bits as (2p+1)^2, it might give some possibilities to eliminate.)