Continuity of Primes
 

With all of the various ways to generate primes (Riesel, Proth, Mersenne etc) there seems to be quite a few "gaps" that must occur in the "plain old" primes that can't be expressed with an elegant, concise formula that lends itself to fast primality proving.

Is there any such list of "known continuous primes" where all the primes < P have been identified?

That would be the real "No Primes Left Behind" effort I would think.

[url]http://primes.utm.edu/notes/faq/LongestList.html[/url]

Primegrid had a subproject that found contiuous primes. They ended up with with many dvds of data.

Here you can find the first 10[SUP]12[/SUP] primes up to 3*10[SUP]13[/SUP]:
[URL="http://primes.utm.edu/nthprime/"]http://primes.utm.edu/nthprime/[/URL]

[QUOTE=Mr. P-1;267641][URL]http://primes.utm.edu/notes/faq/LongestList.html[/URL][/QUOTE]

So I guess that means when we "discover" primes of the various forms, they are much larger than the primes that are known to exist in continuity, and therefore they are "real discoveries," in a manner of speaking.

If that is true, each prime is probably a unique find.

Correct?

[QUOTE=LiquidNitrogen;267910]So I guess that means when we "discover" primes of the various forms, they are much larger than the primes that are known to exist in continuity, and therefore they are "real discoveries," in a manner of speaking.[/QUOTE]

According to the article: "At the time I last updated this page, these projects had found (but not stored) all the prime up to 10^18, but not yet to 10^19."

If you expended 100 times as much effort, you might get up to 10^21. If you devoted the entire world's computer resources to the project, you could probably push it well past 10^30.

You'd never, ever, reach this 100 digit prime:

3664461208681099176204078925954510073897620111029087350504719136242910190767917650858670935504633223

[QUOTE]If that is true, each prime is probably a unique find.[/QUOTE]

I don't know what you mean by "unique" in this context. Here's the next one:

3664461208681099176204078925954510073897620111029087350504719136242910190767917650858670935504633509

Both took a fraction of a second to generate on my computer. Neither, in all probability, has ever been "discovered" before.

The primes that are considered "discoveries" are the ones that take significant resources to find

I suggest you read [url=http://primes.utm.edu/prove/index.html]this primer on primality testing[/url]. You'll have a much better understanding of what you see in this forum.

[QUOTE=Mr. P-1;267962]
If you expended 100 times as much effort, you might get up to 10^21. If you devoted the entire world's computer resources to the project, you could probably push it well past 10^30.

You'd never, ever, reach this 100 digit prime:
[/QUOTE]

That makes the point crystal clear. I haven't seen any online resources offering such a concise explanation.

[QUOTE=Mr. P-1;267962]
I don't know what you mean by "unique" in this context.
[/QUOTE]

The first answer you gave answers this one. With such a huge gap in the prime record, there is no way any of the primes we generate here are a part of that continuous list. I thought maybe there were people somewhere who would test the neighborhood of announced primes for primality as well, perhaps "finding" some that might have been shown later.

Now I see that was a stupid assumption!

So each prime that is found is, essentially, a new find. I'd call that a discovery. The large primes you mentioned I would call a "monumental undertaking" as well.


[QUOTE=Mr. P-1;267962]
I suggest you read [URL="http://primes.utm.edu/prove/index.html"]this primer on primality testing[/URL]. You'll have a much better understanding of what you see in this forum.[/QUOTE]

Primer on primes. Nice!

[QUOTE=Mr. P-1;267962]I suggest you read [URL="http://primes.utm.edu/prove/index.html"]this primer on primality testing[/URL]. [/QUOTE]

I did find one typo on [URL]http://primes.utm.edu/prove/prove1.html[/URL]

In 2002 a long standing question was answered: can integers be [B]prove [/B]prime

I think this should be changed to the word [B]proven[/B] there.

And now I actually know how to do the Lucas-Lehmer test, although those s(k) numbers grow too big for Excel after s(4). At least Excel can prove 2^5 - 1 is prime using Lucas-Lehmer :smile:

[QUOTE=LiquidNitrogen;268164]And now I actually know how to do the Lucas-Lehmer test, although those s(k) numbers grow too big for Excel after s(4). At least Excel can prove 2^5 - 1 is prime using Lucas-Lehmer :smile:[/QUOTE]

If you reduce mod the Mersenne number at each step, you can prove 2^19 - 1 prime in Excel.

[QUOTE=CRGreathouse;268184]If you reduce mod the Mersenne number at each step, you can prove 2^19 - 1 prime in Excel.[/QUOTE]

I'm not sure I follow. Here is what I did.

1. Proving p = 2^n - 1 is prime for n = 5, p = 31.
2. S(0) = 4 {defined}
3. Need to generate up to S(n-2) where S(x+1) = [S(x) * S(x)] - 2

3a. S(1) = 4^2 - 2 = 14
3b. S(2) = 14^2 - 2 = 194
3c. S(3) = 194^2 - 2 = 37634

4. Test S(n-2)/p = S(3)/p = 37634/31. If remainder is 0, p is prime.

37634/31 = 1214.0 so p is prime.

What would this involve doing it the way you mentioned?

[QUOTE=LiquidNitrogen;268186]I'm not sure I follow. Here is what I did.

1. Proving p = 2^n - 1 is prime for n = 5, p = 31.
2. S(0) = 4 {defined}
3. Need to generate up to S(n-2) where S(x+1) = [S(x) * S(x)] - 2

3a. S(1) = 4^2 - 2 = 14
3b. S(2) = 14^2 - 2 = 194
3c. S(3) = 194^2 - 2 = 37634

4. Test S(n-2)/p = S(3)/p = 37634/31. If remainder is 0, p is prime.

37634/31 = 1214.0 so p is prime.

What would this involve doing it the way you mentioned?[/QUOTE]3. Need to generate up to S(n-2) where S(x+1) = {[S(x) * S(x)] - 2} mod p

[QUOTE=CRGreathouse;268184]If you reduce mod the Mersenne number at each step, you can prove 2^19 - 1 prime in Excel.[/QUOTE]

If you get the [URL="http://www.immortaltheory.com/NumberTheory/ZMath.htm"]ZMath Addin[/URL], you can confirm 2^607-1 is prime in Excel. You can test up to 2^829-1.

[QUOTE=LiquidNitrogen;268186]What would this involve doing it the way you mentioned?[/QUOTE]

Every time you would square and subtract two, reduce mod p afterward. That way you're never squaring a number larger than p.

[QUOTE=CRGreathouse;268217]Every time you would square and subtract two, reduce mod p afterward. That way you're never squaring a number larger than p.[/QUOTE]

I thought it was mod 2^p-1 okay.

[QUOTE=CRGreathouse;268217]Every time you would square and subtract two, reduce mod p afterward. That way you're never squaring a number larger than p.[/QUOTE]

Ok, so I think I have it now. Is this spreadsheet correct then?

[ATTACH]6875[/ATTACH]

[QUOTE=LiquidNitrogen;268250]Ok, so I think I have it now. Is this spreadsheet correct then?

[ATTACH]6875[/ATTACH][/QUOTE]


as far as I can tell yes. haven't checked the correct values on the way.

[url]http://oeis.org/A095847[/url]

[QUOTE=wblipp;268193]If you get the [URL="http://www.immortaltheory.com/NumberTheory/ZMath.htm"]ZMath Addin[/URL], you can confirm 2^607-1 is prime in Excel. You can test up to 2^829-1.[/QUOTE]

Now that is cool, thanks! Do you have that factor.exe program that is being referred to in the documentation? I went to the website it was linked to, but that site is down now.

Why can't authors just "bundle", all these external links are a drag!

[QUOTE=LiquidNitrogen;268253]Now that is cool, thanks! Do you have that factor.exe program that is being referred to in the documentation? I went to the website it was linked to, but that site is down now.

Why can't authors just "bundle", all these external links are a drag![/QUOTE]

inurl:"factor.exe" might help in google.

[QUOTE=LiquidNitrogen;268164]
And now I actually know how to do the Lucas-Lehmer test, although those s(k) numbers grow too big for Excel after s(4). At least Excel can prove 2^5 - 1 is prime using Lucas-Lehmer :smile:[/QUOTE]

in fact, using 32bit excel you can prove m=2^p-1 is prime for p=31 (and all p smaller, of course), using some tricks, like taking the MOD function each time, after each step (yes, there is a MOD function, you don't need to do division as said in another reply above) and using the fact that x^2=(m-x)^2 mod m (that is, testing after each step and taking the smallest one for squaring), and if you use VBA in excel and declare them as "variants", then you can go to 2^43-1 (that is proved composite). For 64bit excel you can go to prove m=2^p-1 is prime for p=61 (and all other primes p smaller then 61, leading to primes or composite m's) by declaring them as Longlong in VBA (this type is missing in Excel32).

This just for fun :D (no computational value).