Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2009-06-25, 15:53   #1
cipher's Avatar
Feb 2007

211 Posts
Default Calculation for Cunningham Chain 2nd Kind.

I am planning to search Cunningham Chain 2nd for n=100,000. For more info.

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.


P.s: Here is a post where biwema calculated probabilities for Twin prime.
cipher is offline   Reply With Quote
Old 2009-09-01, 15:12   #2
biwema's Avatar
Mar 2004

3×127 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: 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 is offline   Reply With Quote

Thread Tools

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

All times are UTC. The time now is 10:56.

Tue Aug 11 10:56:00 UTC 2020 up 25 days, 6:42, 1 user, load averages: 2.64, 2.54, 2.25

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.