Thread for posting tiny primes

[3.14159]

Originally Posted by CRGreathouse

For some meaning of "guarantee", at least.

Of course as I've said, if you're looking to get that kind of certainty you'd be better off with one Miller-Rabin and a few applications of some modern test, e.g. Damgård-Frandsen; for the time it would take you to do 10 M-Rs (1 M-
R + 3 D-F), you can get higher confidence than you'd get for 30 M-Rs: 1/142657607172096 vs. only 1/1073741824. They're better in the average case, too.

... The actual odds of failure for 30 Miller-Rabin tests is at worst 1 in 4³⁰, which is 1 in 1152921504606846976.

Originally Posted by CRGreathouse

Sure, because ispseudoprime() is stronger. If you want just one test do

ispseudoprime(n, 1)

BPSW. Also, what is their trial factor limit?

[CRGreathouse]

Originally Posted by 3.14159

... The actual odds of failure for 30 Miller-Rabin tests is at worst 1 in 4³⁰, which is 1 in 1152921504606846976.

Sorry, copying between too many screens. I'll let you look up better limits for various tests (depending, in some cases, on the value of n mod 4 and how many tests you do) if you really care about the right answer. In the long run, for every M-R worth of testing you do on these modern tests, you improve the worst case by something like 1/64 rather than 1/4.

[CRGreathouse]

Originally Posted by 3.14159

BPSW. Also, what is their trial factor limit?

Looks like trial division up to 101 (using 2-3 gcd operations rather than 26 divisions):
http://pari.math.u-bordeaux.fr/cgi-b...2380&root=pari

It's in BPSW_psp(GEN N).

[3.14159]

Originally Posted by CRGreathouse

I didn't follow that, what's the question? What do you mean by polynomial tests? Aren't *what* supposed to prove a number prime? (Surely not a function named ispseudoprime()...?)

Nevermind, I didn't understand what I posted either. I'm deleting that post.

[3.14159]

Also: For the sieving in k * 2²⁵⁶⁷²⁰ + 1, I've sieved up to 4 * 10¹². For k * 113²⁸⁷²⁰ + 1, I've sieved up to 9.28 * 10¹¹ .

My range is in between 500 and 780000, so I checked for the exponent in the Proth Search database to ensure I would not bump into any previously discovered prime numbers. Luckily, there have been no primes discovered prior to mine, and the exponent is too small to be considered reserved.

There are just under 15000 candidates left out of the original 389750. (1 in 26.)

[CRGreathouse]

Originally Posted by axn

Various projected milestones

p=6.34e12: 1 in 15
p=4.52e13: 1 in 16
p=3.23e14: 1 in 17
p=2.30e15: 1 in 18
p=1.64e16: 1 in 19
p=1.17e17: 1 in 20

PS:- These numbers are specific for your current sieve.

How do you calculate these for a given sieve? I know how to estimate (and even calculate, for small limits) the efficiency of a general sieve over a large region, but what adaptations do you make for particular exponents?

[axn]

Originally Posted by CRGreathouse

How do you calculate these for a given sieve? I know how to estimate (and even calculate, for small limits) the efficiency of a general sieve over a large region, but what adaptations do you make for particular exponents?

Exponents? Nothing. Base. Now that's the ticket!

All I do is a straight application of Merten's theorem, plus accounting for forced factors (well, non-factors).

His search used base 12096, which removes 2,3,7.

[CRGreathouse]

Originally Posted by axn

Exponents? Nothing. Base. Now that's the ticket!

Yeah... brainfart. That's what I meant.

Originally Posted by axn

All I do is a straight application of Merten's theorem, plus accounting for forced factors (well, non-factors).

Did you see P. Dusart's recent paper on the arXiv? It has quite good effective bounds on Mertens' Theorem. (I emailed the author with a minor error in the preprint; he hasn't responded yet, though. I hope I used the right address!)

[3.14159]

Submissions:

13991459166294200349680409140910964331078980374838150413700111716409694957060219658540447446756804361737932171824532662997234491730381614642363532665776678394716892240574049843516456950533421259405132328505718016034215746811533357813986959213666784945588235540252623517564817527633474134033298838625662883505013729651558589056101205323970721955962415337977073133649083350457715256417602450217117774622497307698691202557586313846613095334028019780818625804565991075363703402520377598825424912508289232694776392688553780878438641711046390631490071444361097202489902969407082807657017476878281826626913717898537100746516117738676468945127219151744799867002319817032153856297965631021611064597836390940853102170519838315128163398914072476606006303098534758983771427620885590501903178419997114479326261985894431130402237332691663179096260355771163447795362667420490977580311242677753460711830695283208804907464711639297673965718581883688202164764327343211649282543591248714175220876925095188511669958610763031058502568100805190761741005184892572051797330336944497775895745769809988299792529995616223239672145430849270728473247859123784388391310947496824092753429167605879966442789885851797572329967067607025388711741412892934718553465970838546320888270553454010551015781225521167085537543623092504674044423624936309832247671763656052062372104699888960577966799051015709888160537102583143464105996295290949721364403491851778570038395589091148873133068821041657761628525480567471055398173749590909327604976655322152443559492236244699816812255644465066816667652348468356020617378207978659136929793 (1589 digits)

[3.14159]

Also: Testing for k * 2²⁵⁶⁷²⁰ + 1

It tempts me to look for a 10⁵-digit prime... (The above range is only 77284 to 77287 digits)

Submissions: (I won't be listing amount of decimal digits anymore):

5913*2^7560+1
9387*2^7560+1
25495*2^7560+1
11761*2^15560+1
15283*2^15560+1
18993*2^15560+1
3627*2^21820+1
4933*2^21820+1
7483*2^21820+1
34021*2^21820+1
40233*2^21820+1
61285*2^21820+1
71511*2^21820+1
76381*2^21820+1
6615*2^5260+1
9373*2^5260+1
19333*2^5260+1
19341*2^5260+1
20743*2^5260+1

[3.14159]

Also: I remember downloading an app which sieved for Generalized Fermat numbers. Unfortunately, it was over at the second computer. I looked everywhere for it, and unfortunately could not remember where I downloaded it from. Note that it was not command-lined, but a separate app, like NewPGen and MultiSieve.

If anyone manages to find the app, post the link.

Update: Methinks I found it, although I face limited/no connectivity.
Update, again: Nope. Fluke.
Update, again: File found