Sixth Prime Came on Schedule

[wblipp]

From a closed thread:

I've previously used a model for the original 17 values and their individual start points that gives the probability of finding "j" primes by level n. One way to define the doorway for when the jth prime "should" appear is the period when the most likely number of primes found is "j".

1st 800K-1.1M
2nd 1.1M-1.6M
3rd 1.6M-2.2M
4th 2.2M-3.1M
5th 3.1M-4.4M
6th 4.4M-6.5M
7th 6.5M-10.1M
8th 10.1M-16.8M
9th 16.8M-29.5M
10th 29.5M-57M
11th 57M-127M
12th 127M-344M
13th 344M-1.2G
14th 1.2G-7.2G
15th 7.2G-108G
16th 108G-18T
17th above 18T

The Sixth came in the middle of its doorway.

[jjjjL]

I guess it did.

Hopefully the 7th 8th 9th and 10th are all in the 8th's window the way the 2nd, 3rd, 4th, and 5th were all in the 1st and 2nd.

I'm somehow not surpised that one of these predictions worked. Enough predictions were made that one of them had to be right.

-Louie

[Keroberts1]

Do these look different if regenerated and updated to account for not finding primes up to certain values. If you don't mind me wanting to know where this stands right now.

[wblipp]

Originally posted by Keroberts1
Do these look different if regenerated and updated to account for not finding primes up to certain values. If you don't mind me wanting to know where this stands right now.

Right now, with the sixth prime coming right where this model predicted, the results would not be a lot different. Back when I was updating these calculations on a regular basis, people were unhappy with the phenomenon that the most likely time kept receeding. It's true but counterintuitive for many people, including Louie. It's true because as you keep chopping off near times when the prime might have been found, the average of the remaining times keeps getting larger.

[Keroberts1]

From my understanding ok the likelyness of primes in certain regions and for certain K values I'd expect the final completion date would depend mostly upon the day we find a prime for 67607 because it is the one with the lowest proth weight. Am i correct in assuming that if a prime is found for this K value then the top numbers would come down a bit below 18T?

I guess it is expected that this project should take a long time then but at the same time the proth weights of the first few didn't come in order and we could always get lucky again and find a couple in a short amount of time.

side note

I'm not exactly a math wiz I've only made it up to multi-variable calc and i have never done any work with modular arithmatic, however I do have an insatiable curiosity and if anyone would be able to point out a couple places (preferable online) where i might be able to find some information about the math involved in the project... proth prime testing, sieving techniques, P-1 factoring and even a little info on how these predictions were made I'd be happy to check them out. I've just gotten out on break and i have alot of time on my hand. I'd love to spend some time learning some of this, if for no other reason than because i have nothing better to do until school starts again.

[ceselb]

The mersenne forum (http://www.mersenneforum.org/) is a good place to spend a couple of hours (or days :)).

[kugano]

Yeah, GIMPS (mersenne.org) is a good place to start. The following link talks about trial division and P-1 factoring, both of which are mostly done as sub-projects by people here on the forums (from the main forum page, check out the "Sieving" and "Factoring" sub-forums). Also, while the following page talks about the Lucas-Lehmer test, we use Proth's algorithm instead.
<http://www.mersenne.org/math.htm>

Eric Weisstein's Mathworld describes Proth's Theorem, although it doesn't give much of a derivation:
<http://mathworld.wolfram.com/ProthsTheorem.html>
You can find lots of other information on various primality tests in the Mathematics > Number Theory > Prime Numbers category at Mathworld.

Chris Caldwell's Prime Pages have some very good intermediate-level descriptions of modern primality tests. It might be more readable than Mathworld, which is more of a reference encyclopedia and less of a tutorial.
<http://primes.utm.edu/prove/index.html>

Should be enough to get you started ... enjoy!

--
David Norris
danorris@seventeenorbust.com

[kuroyama1]

Can anyone tell me where to find some theory, such as where the 6th prime would be found? I've got a few theory ideas myself, but don't feel like repeating what others have said.

For instance, I predict that in order to Sieve with the number 5359 down to where 26449 Proth tests sufficed to find 5359•2^5054502+1 is prime (as was done), it was necessary to sieve out all potential factors below around 130 billion, where the sieve eliminates all exponents 'n' such that 5359*2^n+1 is divisible by a number below 130 billion. How close is this to reality?

I wrote my own little sieve. On a 3GHz machine, with any one of the 17 numbers, it takes about a day to sieve out all exponents (up to 20 million) for which there is a factor below 1 billion. I'm sure your sieve is probably faster, but if there is anywhere to find the theory then I can see if any of my math tricks were new (and potentially useful) or not.

[wblipp]

Originally posted by kuroyama1
Can anyone tell me where to find some theory, such as where the 6th prime would be found? I've got a few theory ideas myself, but don't feel like repeating what others have said.

These is some discussion about models for SOB estimates in the thread on A Resource Allocation Model (http://www.free-dc.org/forum/showthread.php?s=&threadid=2988) and the thread on A New Estimate for finding Primes above 3M (http://www.free-dc.org/forum/showthread.php?s=&threadid=2884). Be aware that late in the second thread we conclude the first part is mostly rubbish - a poor and awkward estimate of Proth Weights that can more easily be looked up in Gallot's paper (http://perso.wanadoo.fr/yves.gallot/papers/weight.pdf) or calculated with Brennan's applet (http://www.brennen.net/primes/ProthWeight.html) (they differ by a factor of 2 because they use different definitions of weight).

The core of these estimates is
1. The probability that any one value of (k,n) is prime is a proth-weight adjusted Prime Number Theorem value
2. For a fixed K, the expected number of primes from n1 to n2 is the sum of the probabilities in part 1, which is adequately approximated by the integral.
3. If the expected number of primes in a range is "x", the Poisson approximation gives a good estimated of the probability there are zero (or one or two or three) primes in the range. For zero, this is exp(-x).
4. The k values are independent, so the probability of "i" primes can be found by combining the the probability of zero or not-zero primes for each k (we don't care about 2 or 3 primes for the same k).

Note that sieving has no impact on the range where primes will be found, only on the amount of time it will take to find them. A Proth-weight adjusted Merten's Theorem works well for estimating the number of factors to be found by sieving.

William