mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2011-11-06, 18:52   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default 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.
wblipp is offline   Reply With Quote
Old 2011-11-07, 02:16   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

212548 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
LaurV is offline   Reply With Quote
Old 2011-11-08, 15:21   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Today a spotted (721^457-1)/720, which needed the algebraic factors of 721^456-1 to complete the N-1 proof.
wblipp is offline   Reply With Quote
Old 2011-11-08, 15:31   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-08, 19:35   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1013110 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2011-11-08, 19:45   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-08, 20:14   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2011-11-08, 20:19   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44448 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
wblipp is offline   Reply With Quote
Old 2011-11-08, 22:41   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-09, 02:43   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
wblipp is offline   Reply With Quote
Old 2011-11-09, 04:24   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts
Default

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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:00.

Sat Oct 31 08:00:12 UTC 2020 up 51 days, 5:11, 2 users, load averages: 1.25, 1.45, 1.62

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.