mersenneforum.org Share N+/-1 Primality Proofs
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-06, 18:52 #1 wblipp     "William" May 2003 New Haven 45018 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-07, 02:16   #2
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

22×5×17×29 Posts

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

 2011-11-08, 15:21 #3 wblipp     "William" May 2003 New Haven 23·103 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-08, 15:31   #4
R.D. Silverman

Nov 2003

164448 Posts

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.

2011-11-08, 19:35   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2B7916 Posts

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

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

Nov 2003

11101001001002 Posts

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.

 2011-11-08, 20:14 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,229 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
2011-11-08, 20:19   #8
wblipp

"William"
May 2003
New Haven

23×103 Posts

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.

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

Nov 2003

22·5·373 Posts

Quote:
I was not questioning doing the primality tests. I was questioning why one
available and are no harder to use.

2011-11-09, 02:43   #10
wblipp

"William"
May 2003
New Haven

23×103 Posts

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?

 2011-11-09, 04:24 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,229 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post James Heinrich Math 57 2011-09-12 14:16 cheesehead Soap Box 71 2010-01-14 09:04 spkarra PrimeNet 4 2009-11-20 03:54 Brian-E Information & Answers 7 2007-08-02 23:15 Orgasmic Troll Math 1 2004-12-30 15:10

All times are UTC. The time now is 20:49.

Wed Jan 19 20:49:07 UTC 2022 up 180 days, 15:18, 1 user, load averages: 1.49, 1.33, 1.24

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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐