Davieddy's World

[davieddy]

Originally Posted by Aramis Wyler

Expected LL work saved TFing 1 expo from 71 to 75 is 1/72+1/73+1/74+1/75 = .054

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^x*e^-E/x!
Note that the sum from x=0 to infinity is 1.

P(0) = e^-E
P(1) = E*e^-E
P(>0) = 1 - e^-E

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^-E = .054 - .0015....
so the error in this case is neither very obvious nor serious.


David

[Aramis Wyler]

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.

Originally Posted by R.D. Silverman

When is it legitimate to add the probabilities?

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.

Originally Posted by davieddy

1 - e-E = .054 - .0015...

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.

[davieddy]

x and y are primes between 2⁷¹ and 2⁷⁵.
Choose a random number N between 2^60,000,000 and 2^65,000,000.
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.

[Aramis Wyler]

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.

[davieddy]

Originally Posted by Aramis Wyler

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.

I didn't realize that Chalsall was altering the factorization of composites at will.
That guy really is the Devil incarnate!

[chalsall]

Originally Posted by Aramis Wyler

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.

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

Originally Posted by Isacc Asimov

The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!' but 'That's funny...'

[davieddy]

Originally Posted by R.D. Silverman

Clueless.
He ADDED four probabilities. But they were NOT independent!

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⁷¹ and 2⁷⁵ is the integral of 1/(xlnx) = ln(75/71).
Probability of no factors is e^-ln(75/71) = 71/75

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

David

[TheJudger]

Originally Posted by davieddy

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

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^n-1 and 2ⁿ 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₂(m) bitlevels, 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₂(m)*1/log₂(m) = 1 + 1 + 1 + ... + 1 = log₂(m)


Oliver

[henryzz]

Originally Posted by Aramis Wyler

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'm sitting in front of a computer. 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.

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.

[davieddy]

Probability of no factors between 2^n-1 and 2ⁿ = (n-1)/n is a special case of the probability of no factors between a^A and a^B = A/B
from which it follows immediately that the probability of no factors between 2⁷¹ and 2⁷⁵ is 71/75.
(Even more immediately than (71/72)*(72/73)*(73/74)*(74/75) = 71/75)

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^60,000,000 and 2^65,000,000, 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^A and a^B 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_n being a factor still 1/p_n even if we know none of p₁ to p_n-1 divide N?

2) The form of Mersenne factors

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

David

[science_man_88]

Originally Posted by davieddy

Probability of no factors between 2^n-1 and 2ⁿ = (n-1)/n is a special case of the probability of no factors between a^A and a^B = A/B
from which it follows immediately that the probability of no factors between 2⁷¹ and 2⁷⁵ is 71/75.
(Even more immediately than (71/72)*(72/73)*(73/74)*(74/75) = 71/75)

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⁶⁰ and 2⁶⁵, 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^A and a^B 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

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.)