Share N+/-1 Primality Proofs

wblipp · 2011-11-06, 18:52

This thread is for sharing N+/-1 primality proofs completed in the factordb. It's purpose is to share the fun and encourage others to take up the hobby.

Today I spotted (305^617-1)/304 in the PRP list. N-1 is (305^616-1)/304, which has many algebraic factors although the factordb doesn't find them. I added enough of these to N-1 to complete the primality proof.

It used to be easy to spot situations like this, but between the recent increase in the minimum level of PRPs and careful scanning of a few people, they are getting harder to find.

LaurV · 2011-11-07, 02:16

Quote:

Originally Posted by wblipp

Today I spotted (305^617-1)/304 in the PRP list. N-1 is (305^616-1)/304

Technically, N-1 is 305*(305^616-1)/304 :P

wblipp · 2011-11-08, 15:21

Today a spotted (721^457-1)/720, which needed the algebraic factors of 721^456-1 to complete the N-1 proof.

R.D. Silverman · 2011-11-08, 15:31

Quote:

Originally Posted by wblipp

Today a spotted (721^457-1)/720, which needed the algebraic factors of 721^456-1 to complete the N-1 proof.

Why do you bother with obsolete methods to prove the primality of smallish
numbers that are easily dealt with by more modern methods???

It is pointless.

xilman · 2011-11-08, 19:35

Quote:

Originally Posted by R.D. Silverman

Why do you bother with obsolete methods to prove the primality of smallish
numbers that are easily dealt with by more modern methods???

It is pointless.

Possibly because it's easier? This may or may not be the case in the present instance.

Quite often I optimize human time over CPU time.

Paul

R.D. Silverman · 2011-11-08, 19:45

Quote:

Originally Posted by xilman

Possibly because it's easier? This may or may not be the case in the present instance.

Quite often I optimize human time over CPU time.

Paul

Certainly. But APR-CL is just "fire and forget". OTOH, it does require
greater mathematical knowledge if one is writing the source code.

Note also that APR-CL can/does take advantage of known factors of N+1
and/or N-1 to speed the computation.

Batalov · 2011-11-08, 20:14

CHG is also fun to use at about 26 to 27% N+/-1 factored... just like solving a sudoku at a coffee break. (above 27%, it is simply not fun anymore :-) )

Example: 110·R5382-1 is prime. Proven with CHG. (not in FactorDB.)

wblipp · 2011-11-08, 20:19

Quote:

Originally Posted by R.D. Silverman

Why do you bother with obsolete methods to prove the primality of smallish numbers that are easily dealt with by more modern methods???

It is pointless.

Your question is ambiguous. I don't know if you are asking why I, William, am doing this, or why the factordb is doing this. (Actually, I suspect that you don't care about either, and are merely using the guise of a question to share your wisdom on the matter, but I'll grant you the courtesy of acting as if you care about the answers to questions you ask)

Everybody dealing with archiving primality proofs picks a threshold of "below here is trivial and left as exercise for the reader, above here I archive the proof. For his site about Titanic Prime Generalized Repunits, Andy Steward uses 250 digits - all helper primes above that length have proofs on his web site, but below that there is only the assertion that they have been proven. The factordb uses a 300 digit cutoff. Below this the factordb detects PRPs, marks them as PRP in the database, then schedules a proof. Upon passing the proof, the status is changed from PRP to P. Above this level the factordb support N+/-1 proofs and ECPP certificates. The helper files and certificates can be downloaded by anybody wanting to verify the proof.

There is a database report that shows the PRPs, and an interface to download these. There are people who download these, generate Primo proofs, and upload the certificates. I generate these proofs in part because it is even more pointless to generate an ECPP proof for a number with easily detected N+1 and N-1 factors. In addition, I get a kick out of seeing the status change from PRP to P.

Yes pointless - but most of I what I do at MersenneForum is pointless. I don't let that stop me.

R.D. Silverman · 2011-11-08, 22:41

Quote:

Originally Posted by wblipp

Your question is ambiguous. I don't know if you are asking why I, William, am doing this, or why the factordb is doing this. (Actually, I suspect that you don't care about either, and are merely using the guise of a question to share your wisdom on the matter, but I'll grant you the courtesy of acting as if you care about the answers to questions you ask)

Everybody dealing with archiving primality proofs picks a threshold of "below here is trivial and left as exercise for the reader, above here I archive the proof. For his site about Titanic Prime Generalized Repunits, Andy Steward uses 250 digits - all helper primes above that length have proofs on his web site, but below that there is only the assertion that they have been proven. The factordb uses a 300 digit cutoff. Below this the factordb detects PRPs, marks them as PRP in the database, then schedules a proof. Upon passing the proof, the status is changed from PRP to P. Above this level the factordb support N+/-1 proofs and ECPP certificates. The helper files and certificates can be downloaded by anybody wanting to verify the proof.

There is a database report that shows the PRPs, and an interface to download these. There are people who download these, generate Primo proofs, and upload the certificates. I generate these proofs in part because it is even more pointless to generate an ECPP proof for a number with easily detected N+1 and N-1 factors. In addition, I get a kick out of seeing the status change from PRP to P.

Yes pointless - but most of I what I do at MersenneForum is pointless. I don't let that stop me.

I was not questioning doing the primality tests. I was questioning why one
would use obsolete methods when newer/better methods are readily
available and are no harder to use.

wblipp · 2011-11-09, 02:43

Quote:

Originally Posted by R.D. Silverman

I was not questioning doing the primality tests. I was questioning why one would use obsolete methods when newer/better methods are readily available and are no harder to use.

Perhaps Syd, the creator of factordb, will respond. I'll wrap up with an observation and a question.

Observation: There is an elegance about using factorization based proofs in a system that is dedicated to storing factorizations. Much of the infrastructure needed to create the proofs is already designed into the core of the system.

Question: What primality proving method do you recommend for (721^457-1)/720?

Batalov · 2011-11-09, 04:24

Question-variant 2: What primality proving method do you recommend for (721^461-1)/720 (the next PRP in the same (721^n-1)/720 series)?

CHG would work, but Primo is also fast for this size.

For Syd: there's a CHG verifying script by D.Broadhurst; so CHG certificates could also be accepted for download.

2011-11-06, 18:52	#1
wblipp "William" May 2003 New Haven 3·7·113 Posts	Share N+/-1 Primality Proofs This thread is for sharing N+/-1 primality proofs completed in the factordb. It's purpose is to share the fun and encourage others to take up the hobby. Today I spotted (305^617-1)/304 in the PRP list. N-1 is (305^616-1)/304, which has many algebraic factors although the factordb doesn't find them. I added enough of these to N-1 to complete the primality proof. It used to be easy to spot situations like this, but between the recent increase in the minimum level of PRPs and careful scanning of a few people, they are getting harder to find.

2011-11-08, 20:14	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11×911 Posts	CHG is also fun to use at about 26 to 27% N+/-1 factored... just like solving a sudoku at a coffee break. (above 27%, it is simply not fun anymore :-) ) Example: 110·R5382-1 is prime. Proven with CHG. (not in FactorDB.) Last fiddled with by Batalov on 2011-11-08 at 20:19 Reason: Example

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Can two Mersenne numbers share a factor?	James Heinrich	Math	57	2011-09-12 14:16
Avoidance of self- & other-deception in proofs	cheesehead	Soap Box	71	2010-01-14 09:04
Curious and want to share about Prime number 23	spkarra	PrimeNet	4	2009-11-20 03:54
Status of GIMPS proofs	Brian-E	Information & Answers	7	2007-08-02 23:15
Collection of Proofs?	Orgasmic Troll	Math	1	2004-12-30 15:10

2011-11-08, 15:21	#3
wblipp "William" May 2003 New Haven 3×7×113 Posts	Today a spotted (721^457-1)/720, which needed the algebraic factors of 721^456-1 to complete the N-1 proof.

2011-11-09, 04:24	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11×911 Posts	Question-variant 2: What primality proving method do you recommend for (721^461-1)/720 (the next PRP in the same (721^n-1)/720 series)? CHG would work, but Primo is also fast for this size. For Syd: there's a CHG verifying script by D.Broadhurst; so CHG certificates could also be accepted for download.