## Other

drummers-lowrise

Message boards : General discussion : Is there a 'probability of finding a prime' listed anywhere?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message

Joined: 28 Feb 18
Posts: 284
ID: 984171
Credit: 182,080,291
RAC: 0

Message 115997 - Posted: 13 Mar 2018 | 23:29:18 UTC

Just wondering?

I'm fairly new to PrimeGrid and have approx 5 bronze and 1 Turquoise badge. I was just wondering if there is an 'overall' probability of finding a prime listed for each sub-project.

EG: 321 Prime search AVG 1 prime per 52,345 credit, Proth Prime search AVG 1 prime per 1,234 credit

It would give me some idea of how I'm tracking

(I also realise that a prime could be found with 1 credit or with 1 billion credits, but the average would be nice to know)

Thanx

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13650
ID: 53948
Credit: 285,549,128
RAC: 40,408

Message 115998 - Posted: 14 Mar 2018 | 0:13:59 UTC

The larger a number is, the harder it is to find a prime. The difficulty of finding a prime is roughly proportional to X^3 * ln(X), where X is the number of digits in the prime. So it's about 3000 times harder to find a million digit prime than it is to find a prime with one hundred thousand digits. This takes into account both the fact that larger primes are much rarer as well as taking much longer to run each individual test.

While I've never expressed it in terms of credit, on the smaller primes we do sometimes check the odds of a single test being prime.

The four smallest of our primality testing projects are, in order, GFN-15, SGS, PPSE, and GFN-16. As of last month, the odds of finding a prime in PPSE was about 1 in 14 thousand tests, and the odds of finding a GFN-16 were about 1 in 16 thousand tests. Those numbers are approximately 450 thousand and 500 thousand digits long, respectively.

Let's say your computer can do a PPSE test in 5 minutes. On average, then, you could expect to find one PPSE prime after about 48 days of testing.

We can extrapolate those odds for, say the ESP project. ESP numbers are about 7 times larger than PPSE, so it should take 7^3 * ln(7) times as long to find an ESP prime. That's 667 times longer, or 32037 days or about 88 years.
____________
My lucky number is 75898524288+1

Joined: 28 Feb 18
Posts: 284
ID: 984171
Credit: 182,080,291
RAC: 0

Message 115999 - Posted: 14 Mar 2018 | 0:32:44 UTC - in response to Message 115998.

Thanx for the explanation Michael.

You say you don't express in 'credits', you use 'tests' instead, are 'tests' equivalent to WU's?

Thanx again

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13650
ID: 53948
Credit: 285,549,128
RAC: 40,408

Message 116000 - Posted: 14 Mar 2018 | 0:51:57 UTC - in response to Message 115999.

Thanx for the explanation Michael.

You say you don't express in 'credits', you use 'tests' instead, are 'tests' equivalent to WU's?

Thanx again

Yes.
____________
My lucky number is 75898524288+1

axn
Volunteer developer

Joined: 29 Dec 07
Posts: 285
ID: 16874
Credit: 28,027,106
RAC: 0

Message 116004 - Posted: 14 Mar 2018 | 8:50:03 UTC - in response to Message 115998.

So it's about 3000 times harder to find a million digit prime than it is to find a prime with one hundred thousand digits.
<snip>
ESP numbers are about 7 times larger than PPSE, so it should take 7^3 * ln(7) times as long to find an ESP prime. That's 667 times longer, or 32037 days or about 88 years.

FYI, this is not how logs work. ln(x)/ln(y) <> ln(x/y). Of course, the answer is still in the right ball park (since the cube term is the dominant one).

[There is a bigger issue, in that, the size of the numbers are not fixed -- they grow. Hence the odds keep getting worse. Particularly severe for "sparse" projects like the conjecture ones]

mackerel
Volunteer tester

Joined: 2 Oct 08
Posts: 2536
ID: 29980
Credit: 494,291,084
RAC: 3,328

Message 116005 - Posted: 14 Mar 2018 | 9:25:12 UTC - in response to Message 115998.

The four smallest of our primality testing projects are, in order, GFN-15, SGS, PPSE, and GFN-16. As of last month, the odds of finding a prime in PPSE was about 1 in 14 thousand tests, and the odds of finding a GFN-16 were about 1 in 16 thousand tests. Those numbers are approximately 450 thousand and 500 thousand digits long, respectively.

Time for some statistical fail on my part. Are the odds above calculated from the earlier formula, or worked out from actual testing?

If we use the general formula, would sieving affect the practical outcome? Say you have a test range of candidates (pre-sieve), you could work out how many primes to expect in that range. After sieving, you would have the same number of expected primes, but a much shorter candidate list.

I didn't take statistics courses when offered as I thought I'd suck at it. Or do I suck at it because I didn't take those courses? Self fulfilling prophecy.

JeppeSN

Joined: 5 Apr 14
Posts: 1536
ID: 306875
Credit: 35,694,043
RAC: 9,168

Message 116006 - Posted: 14 Mar 2018 | 9:34:12 UTC - in response to Message 116004.

ESP numbers are about 7 times larger than PPSE, so it should take 7^3 * ln(7) times as long to find an ESP prime. That's 667 times longer, or 32037 days or about 88 years.

FYI, this is not how logs work. ln(x)/ln(y) <> ln(x/y). Of course, the answer is still in the right ball park (since the cube term is the dominant one).

Right! If it goes as X^3 * ln X, it would be

(7X)^3 * ln (7X) = 7^3 * X^3 * (ln X + ln 7)

Since the ln 7 term will be negligible, it is more like 7^3 = 343 times slower.

/JeppeSN

Scott Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2270
ID: 1178
Credit: 11,772,852,856
RAC: 13,185,936

Message 116010 - Posted: 14 Mar 2018 | 11:20:17 UTC - in response to Message 116004.

[There is a bigger issue, in that, the size of the numbers are not fixed -- they grow. Hence the odds keep getting worse. Particularly severe for "sparse" projects like the conjecture ones]

I have often wondered about this in the sense that conjecture projects probably don't follow the same pattern as others. More specifically, assuming that the base of users doesn't change drastically (a safer assumption on conjectures where many users have particularly dedicated interests in such projects), as primes are found within a conjecture (thereby often reducing the number of candidates to be tested substantially), I suspect that the odds getting worse as primes grow is actually less severe than in non-conjecture projects (or at least follows a far less smoothed growth and potentially could even experience very slight, brief declines...at least in application if not in theory).

Crun-chi
Volunteer tester

Joined: 25 Nov 09
Posts: 3070
ID: 50683
Credit: 63,378,402
RAC: 148

Message 116043 - Posted: 16 Mar 2018 | 11:03:58 UTC - in response to Message 116010.

Scott, I think that primes in CRUS bases also follow this rule, but since all prime searching stopped in then time when prime is found that is difficulty to prove.
On the other hand: I found primes on CRUS bases when it wasn't expected at all, and also cannot find prime in other bases where I should ( by prediction) find prime long time ago. So primes follows first rule: nobody doesn't know position ( where prime is located)
Also I found big difference in predicted number of primes, and real number in near-repdigit primes. But once again: it follow first rule :)
So CRUS maybe look "different" then other bases, but in real life it is just little more different then any other sequence we all search.
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Message boards : General discussion : Is there a 'probability of finding a prime' listed anywhere?