Calculation for Cunningham Chain 2nd Kind.

cipher · 2009-06-25, 15:53

Hello,
I am planning to search Cunningham Chain 2nd for n=100,000. For more info.
http://primes.utm.edu/top20/page.php?id=20

Can some one calculate the range of K i need to LLR/Sieve for me to have a chance of finding a CC 2nd prime for n=100k.

For example LLR/Sieve k=10G to have 90% chance or each CC2nd prime occurs every 5G for n=100k.

If you can also explain your step of calculation of occurrence of prime probability it will be great appreciated.

Thanks
Cipher.

P.s: Here is a post where biwema calculated probabilities for Twin prime.
http://www.mersenneforum.org/showpos...&postcount=146

biwema · 2009-09-01, 15:12

The probability of constellations of primes (twins, CC etc.) is quite difficult to calculate.
In this case I am sieving to some extent (for example 1 Million or 1 Billion).
At this point all primes of the constellation are (almost) independent. So I can just square the probability of one number being prime.
This way also prevents the influence of different weights etc.

In your case we have for example CC: k*2^100000+1 and k*2^100001+1.
Sieving a Range of k=1..1000000 (500000 candidates) leaves 705 candidates after sieving up to 35 Bit (34.5 billion).

The probability of one number being prime is about 35/50000 (0.07%) (means no factor between 35 bit and sqrt (number). For a constellation of 2 we can square this probability:
Expect 49 CC in 100000000 candidates (or about 1 in 2040816 candidates)

If you test 2040816 candidates the chance of finding at least one CC is 1-1/e or 63.2%
If you test 4081632 candidates the chance of finding at least one CC is 1-1/(e^2) or 86.5%
A 90% Chance you get if you test 2040816* ln(10) candidates, that are about 4.7 Million.
A 99% Chance you get if you test 2040816* ln(100) candidates, that are about 9.4 Million.

A range 1000000 gives 705 Candidates. For 4.7 Million Candidates i recommend you sieving a range of 6.66 Billion. (4.7Million / 705)

Note 1: when you sieve to a higher level, fewer candidates are remaining, but the probability of being prime also increases.
The chance to find a CC in that range is still the same.

Note 2: Some people recommend special k or n for testing because they are more dense. That means that after beginning of sieving more candidates remain.
After all there is no advantage, you can just sieve a larger range which takes the same time (horizontal).
After sieving you habe still to test (on average) the same number of candidates to find a prime.

I hope i made no mistake in my calculations

Good luck
biwema

2009-06-25, 15:53	#1
cipher Feb 2007 323₈ Posts	Calculation for Cunningham Chain 2nd Kind. Hello, I am planning to search Cunningham Chain 2nd for n=100,000. For more info. http://primes.utm.edu/top20/page.php?id=20 Can some one calculate the range of K i need to LLR/Sieve for me to have a chance of finding a CC 2nd prime for n=100k. For example LLR/Sieve k=10G to have 90% chance or each CC2nd prime occurs every 5G for n=100k. If you can also explain your step of calculation of occurrence of prime probability it will be great appreciated. Thanks Cipher. P.s: Here is a post where biwema calculated probabilities for Twin prime. http://www.mersenneforum.org/showpos...&postcount=146

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
A Different Kind of a Computer	a1call	Miscellaneous Math	3	2017-06-29 11:15
What kind of number is	pepi37	Information & Answers	2	2015-05-21 20:50
question about a chain of primes	firejuggler	Math	31	2014-01-08 18:28
So, is this some kind of record or what?	schickel	Forum Feedback	18	2011-01-22 20:29
A Kind of Solitaire	davar55	Puzzles	7	2007-09-21 11:24

2009-09-01, 15:12	#2
biwema Mar 2004 17D₁₆ Posts	The probability of constellations of primes (twins, CC etc.) is quite difficult to calculate. In this case I am sieving to some extent (for example 1 Million or 1 Billion). At this point all primes of the constellation are (almost) independent. So I can just square the probability of one number being prime. This way also prevents the influence of different weights etc. In your case we have for example CC: k2^100000+1 and k2^100001+1. Sieving a Range of k=1..1000000 (500000 candidates) leaves 705 candidates after sieving up to 35 Bit (34.5 billion). The probability of one number being prime is about 35/50000 (0.07%) (means no factor between 35 bit and sqrt (number). For a constellation of 2 we can square this probability: Expect 49 CC in 100000000 candidates (or about 1 in 2040816 candidates) If you test 2040816 candidates the chance of finding at least one CC is 1-1/e or 63.2% If you test 4081632 candidates the chance of finding at least one CC is 1-1/(e^2) or 86.5% A 90% Chance you get if you test 2040816* ln(10) candidates, that are about 4.7 Million. A 99% Chance you get if you test 2040816* ln(100) candidates, that are about 9.4 Million. A range 1000000 gives 705 Candidates. For 4.7 Million Candidates i recommend you sieving a range of 6.66 Billion. (4.7Million / 705) Note 1: when you sieve to a higher level, fewer candidates are remaining, but the probability of being prime also increases. The chance to find a CC in that range is still the same. Note 2: Some people recommend special k or n for testing because they are more dense. That means that after beginning of sieving more candidates remain. After all there is no advantage, you can just sieve a larger range which takes the same time (horizontal). After sieving you habe still to test (on average) the same number of candidates to find a prime. I hope i made no mistake in my calculations Good luck biwema