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 [URL="http://factorization.ath.cx/index.php?id=1100000000439188597"](305^617-1)/304[/URL] 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.

[QUOTE=wblipp;277374]
Today I spotted [URL="http://factorization.ath.cx/index.php?id=1100000000439188597"](305^617-1)/304[/URL] in the PRP list. N-1 is (305^616-1)/304[/QUOTE]

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

Today a spotted [URL="http://factorization.ath.cx/index.php?id=1100000000439189717"](721^457-1)/720[/URL], which needed the algebraic factors of 721^456-1 to complete the N-1 proof.

[QUOTE=wblipp;277569]Today a spotted [URL="http://factorization.ath.cx/index.php?id=1100000000439189717"](721^457-1)/720[/URL], which needed the algebraic factors of 721^456-1 to complete the N-1 proof.[/QUOTE]

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.

[QUOTE=R.D. Silverman;277573]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.[/QUOTE]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

[QUOTE=xilman;277607]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[/QUOTE]

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.

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: [URL="http://factordb.com/index.php?query=%2811*10%5E5383-119%29%2F9"]110·R5382-1[/URL] is prime. Proven with CHG. (not in FactorDB.)

[QUOTE=R.D. Silverman;277573]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.[/QUOTE]

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 [URL="http://www.primes.viner-steward.org/andy/titans.html"]Titanic Prime Generalized Repunits[/URL], 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.

[QUOTE=wblipp;277619]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 [URL="http://www.primes.viner-steward.org/andy/titans.html"]Titanic Prime Generalized Repunits[/URL], 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.[/QUOTE]

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.

[QUOTE=R.D. Silverman;277639]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.[/QUOTE]

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

[B]Observation: [/B]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.

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

[B]Question-variant 2: [/B]What primality proving method do you recommend for [URL="http://www.factordb.com/index.php?id=1100000000463281146"](721^461-1)/720[/URL] (the next PRP in the same (721^n-1)/720 series)?

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

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

I think I see the misunderstanding. Bob is imagining that I marshaled factoring effort to find the N-1 factors, and that I am encouraging others to also spend their resources finding factors that are wanted only to make the N-1 proofs. I agree that would be pointless effort. But all I really did was click a few buttons and manually type the expression of a few algebraic factors. The needed factors were all small enough that the factordb "scan" buttons, which run a small amount of ECM, P-1, and P+1, provided sufficient factors to make the proof (It's also possible some of the factors were already in the factordb). At these current size ranges - 1200 to 2000 digits - I see lots of cases where adding the algebraic factors and the scan buttons does not complete a proof. I haven't been mentioning these, nor working on them.

So my question was "What should you do if you already know over 33% factorization of N-1?" I thought Bob was saying there is something better. But Batalov's question is "What should you do if you do NOT have 33% factorization?" Within the context of factordb, the answer to that question is currently "Primo."

[QUOTE=Batalov;277617]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: [URL="http://factordb.com/index.php?query=%2811*10%5E5383-119%29%2F9"]110·R5382-1[/URL] is prime. Proven with CHG. (not in FactorDB.)[/QUOTE]
What's CHG? (Google finds a lot of CHG primality certificates and a lot of unrelated crap, but not an explanation of the method in the first several result pages.)

[QUOTE=wblipp;277672]
So my question was "What should you do if you already know over 33% factorization of N-1?" I thought Bob was saying there is something better. But Batalov's question is "What should you do if you do NOT have 33% factorization?" Within the context of factordb, the answer to that question is currently "Primo."[/QUOTE]

If you know > N^(1/3) factorization of N-1/N+1 then using the combined
Lehmer/Pomerance/Brillhart et.al. thm is [i]fine[/i]. But, as you indicate,
factoring efforts on N-1/N+1 are pointless. I am guilty of failing to
convey this point. Note that APR-CL can take advantage of known
factors of N+1/N-1 to speed its proof.

I am unfamiliar with PRIMO. What method(s) does it employ?

[QUOTE=R.D. Silverman;277692]
I am unfamiliar with PRIMO. What method(s) does it employ?[/QUOTE]

It uses ECPP.
[URL]http://www.ellipsa.eu/public/primo/primo.html[/URL]

[QUOTE=Random Poster;277685]What's CHG? (Google finds a lot of CHG primality certificates and a lot of unrelated crap, but not an explanation of the method in the first several result pages.)[/QUOTE]
Oh, CHG full name is a mouthful. This is Coppersmith--Howgrave-Graham (this is only two people) lattice basis reduction method(s). The implementations are [URL="http://primes.utm.edu/bios/page.php?id=797"]here[/URL] and also
> "...If you do not already have it, my validation script is here:
> [URL="http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp"][COLOR=#247cd4]http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp[/COLOR][/URL]
> \\ Coppersmith--Howgrave-Graham certificate tester, Version 0.8
> \\ David Broadhurst, 3 Mar 2006, with huge help from John Renze"

[QUOTE=Batalov;277722][URL="http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp"][COLOR=#247cd4]http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp[/COLOR][/URL][/QUOTE]That could almost have come from the IOCC competition.

I like it!

Paul

Browsing through the PRPs tonight, I found [URL="http://factorization.ath.cx/index.php?id=1100000000291709216"](10^1662*82-73)/9[/URL]. N-1 is divisible by 10^1662-1. Sufficient factors were previously known to finish the proof.

Just to be clear - what I'm doing is looking the list of [URL="http://factorization.ath.cx/listtype.php?t=1"]already-found PRPs[/URL] in the factordb, searching for ones where a primality proof can be created easily. I do it because it's fun. I share them because I think other people will find it fun, too.

Last night I spotted [URL="http://factorization.ath.cx/index.php?id=1000000000009951494"](10^1470*4-7)/3[/URL]. The N+1 shares the cyclotomic form 10^1470-1, which has many algebraic factors, many of which were already factored or quickly succumbed to the scan button.

I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
[url=http://factordb.com/index.php?id=1100000000271726668](2^2617+1)/3-1[/url] has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).

[QUOTE=debrouxl;278103]I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
[URL="http://factordb.com/index.php?id=1100000000271726668"](2^2617+1)/3-1[/URL] has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).[/QUOTE]
Should be [URL="http://factordb.com/index.php?query=%282%5E2616-1%29"]completely[/URL] factored really. But factorDB doesn't know that these numbers are related, or that [URL="http://factordb.com/index.php?query=%282%5E2616-1%29%2F3"]this[/URL] is related.

Today's proof is a cheat. N=[URL="http://factorization.ath.cx/index.php?id=1100000000464035217"](10^318*911+419)/73082460569797[/URL] is slightly larger the 300 digits. N-1 factored quickly with the scan buttons, having a largest factor a little below 300 digits. Factordb automatically proved the factor of N-1, enabling the proof of N.

How 'bout this? [URL="http://factordb.com/index.php?query=2837%21%5E2%2B2837%21%2B1"]2837!^2+2837!+1[/URL] (a.k.a. Phi(3,2837!) )

This one will be a bit harder (will need some more factoring and a CHG on it) - [URL="http://factordb.com/index.php?query=%282415%21%5E5-1%29%2F%282415%21-1%29"]Phi(5,2415!)[/URL]

These extend [URL="https://oeis.org/A051856"]A051856[/URL] and [URL="https://oeis.org/A200906"]A200906[/URL]

[QUOTE=Batalov;279671]How 'bout this? [URL="http://factordb.com/index.php?query=2837%21%5E2%2B2837%21%2B1"]2837!^2+2837!+1[/URL] (a.k.a. Phi(3,2837!)[/QUOTE]

How'd ya do dat? Factordb says it has an N-1 proof, but N-1 shows no known factors.

Well, in the same way as [URL="http://factordb.com/index.php?query=6001%21%5E2%2B6001%21%2B1"]Phi(3,6001!)[/URL] :-]

(just submitted it to a worker for a PRP test -- and the FactorDB apparently finds all 6001! factors one by one because it takes an inordinate amount of time, but when it does, it realizes that N-1 with the next prime is in order)

Spotted [URL="http://factordb.com/index.php?id=1100000000031611272"](10^1296*13-7)/123[/URL] in the PRP list. Applying the algebraic factors to N-1 was not quite enough to prove it prime, but a few clicks on the scan button provided the one more needed factor.

Another cute one [URL="http://factordb.com/index.php?id=1100000000315170611"](2^5367*7+1)/57[/URL] was proven by N-1 method.

<Taking a break for the night.>

Edit: [URL="http://factordb.com/index.php?id=1100000000004709927"](10^1621*77-41)/729[/URL] by N-1.

[QUOTE=RichD;279900]Another cute one [URL="http://factordb.com/index.php?id=1100000000315170611"](2^5367*7+1)/57[/URL] was proven by N-1 method.

<Taking a break for the night.>

Edit: [URL="http://factordb.com/index.php?id=1100000000004709927"](10^1621*77-41)/729[/URL] by N-1.[/QUOTE]
Well, in the same way as [URL="http://factordb.com/index.php?query=7606%21%5E2%2B7606%21%2B1"]Phi(3,7606!)[/URL] :-]


<Taking a break for the night.>

[URL="http://factordb.com/index.php?query=7076%21%5E2%2B7076%21%2B1"]Phi(3,7076!)[/URL] :-] in fact...

[URL="http://factorization.ath.cx/index.php?id=1100000000291680537"](10^1365*88-97)/9[/URL] by N+1 by adding the algebraic factors of 10^1365-1

[URL="http://factordb.com/index.php?id=1100000000001167959"](5^2498+1)/26[/URL] is proven prime by applying the algebraic factors of 5^2496-1 to N-1.

[URL="http://factordb.com/index.php?id=1100000000349578791"](191*2^6105-1)/381[/URL] is proven prime by applying the algebraic factors of 2^6104-1 to N-1.

[URL="http://factordb.com/index.php?id=1100000000005327544"](10^1900+3)/7[/URL] is proven prime by applying the algebraic factors of 10^1899+1 to N+1.

[QUOTE=Batalov;279952][URL="http://factordb.com/index.php?query=7076%21%5E2%2B7076%21%2B1"]Phi(3,7076!)[/URL] :-] in fact...[/QUOTE]

then ...

[URL="http://factorization.ath.cx/index.php?id=1100000000212781985"]5426!/2713!/2713!+1[/URL] needed some help finding the gazillion tiny factors of N-1.

i.e.

[URL="http://factordb.com/index.php?id=1100000000225099082"]3^3298*2-5[/URL] needed help finding the algebraic factors of 3^3297-1 for the N-1 proof. The big P881 revealed in the algebraic factors was proven by Primo Certificate by klajok on July 26th.

[URL="http://factorization.ath.cx/index.php?id=1100000000294664800"]40^883-39[/URL] needed help finding the algebraic factors of 40^882-1 to complete the N-1 proof.

[URL="http://factorization.ath.cx/index.php?id=1100000000237280068"](2^4518-3)/253[/URL]

N-1 is (2^4518-256)/253 = 256*(2^4810-1)/256.

Factordb needed help seeing the algebraic factors of 2^4801-1.

polcyclo(10,n!) are nice -- their N-1 has factors from n!, n!-1

101!^4-101!^3+101!^2-101!+1
107!^4-107!^3+107!^2-107!+1
267!^4-267!^3+267!^2-267!+1
316!^4-316!^3+316!^2-316!+1

Nudged n!-1 factors into the fDB, now it's time to wait for the small ones to "prove themselves", ...and maybe run C-HG for larger ones.

P.S. polcyclo(15,n!) may need a bit of help, e.g. [URL="http://www.factordb.com/index.php?id=1100000000467529955"]134!^8+134!^5+134!^3+1-134!^7-134!^4-134![/URL] :-)

I've been finding it harder to spot candidates in the PRP list that just need help with algebraic factors and the scan button. This is partly because the list has been picked over, and partly because, with the current wavefront of Primo Proofs in the 1300 digit range, it's rarer for "scan" to be enough help. Today, though, I spotted

[URL="http://factorization.ath.cx/index.php?id=1100000000294465047"]2^4441+17[/URL]

The N-1 includes 2^4437+1, and the algebraic factor 2^(4437/3)+1 had been missed.

Today I found [URL="http://factorization.ath.cx/index.php?id=1100000000291689055"]10^1595-100001[/URL] in the PRP list. N+1 was missing the 10^(1590/3)-1 algebraic factor.

Oh. In this case, there must be a trove of similar known proven primes at M.Kamada's [URL="http://homepage2.nifty.com/m_kamada/math/primesize.zip"]site[/URL]. They are just not in the factorDB.

Tonight I spotted [URL="http://factorization.ath.cx/index.php?id=1100000000349328658"](2^4537*53-1)/105[/URL] in the PRPs. The factordb didn't know that N-1 had algebraic factors in common with 2^4536-1

Near the leading edge of Primo proofs I found, [URL="http://factorization.ath.cx/index.php?id=1100000000294465164"]2^4557+9[/URL]. N-1 needed the algebraic factors of 2^4554+1. I was surprised such an obvious example was still available.

A fun start for the new year: searching among somewhat larger PRPs, I spotted the Wagstaff Prime [URL="http://factorization.ath.cx/index.php?id=1100000000004299235"](2^5807+1)/3[/URL]. Wagstaff primes are especially attractive for these proofs because N+1 and N-1 are Cunningham numbers with different exponents, increasing the likelihood that one of them has lots of algebraic factors. Like most of the proofs I feature in this thread, this one was missing algebraic factors from one side. This hints that a systematic check of Wagstaff Primes may turn up more easily completed proofs in the factordb. The exponents for Wagstaff Primes are [URL="http://oeis.org/A000978"]OEIS Sequence 978[/URL]

I found another of these (2^n +/- a)/b PRPs where a+b or a-b is a power of 2, leading to sufficient algebraic factors for an N+1 or N-1 proof. Today's example was from near the clearing edge of PRPs: [URL="http://factorization.ath.cx/index.php?id=1100000000207996048"](2^4601+7)/39[/URL]

I guess I've not inspired others to browse the PRP list for easy targets. I found this one among the 50 smallest PRPs.

[URL="http://factorization.ath.cx/index.php?id=1100000000031632945"](10^1410*74-11)/63[/URL] - the N-1 cancels the 74, leaving lots of algebraic factors for 10^1410-1.

[URL="http://www.factordb.com/index.php?query=%2810%5E3258-73%29%2F9"](10^3258-73)/9[/URL] via a p1057 and some algebra in N+1

...and [URL="http://www.factordb.com/index.php?query=%2810%5E12891%2B11%29%2F3"](10^12891+11)/3[/URL] with N-1 (these are some old toys)

[URL="http://www.factordb.com/index.php?id=1100000000482470622"]2*911[sup]381[/sup]+1[/URL] via N-1. It's the only prime of the form 2*911[sup]n[/sup]+1 that I've found, other than 1823. I used the factor tables. Here's the link to the table (Near Cunningham):

[URL]http://www.factordb.com/index.php?query=k*b%5En%2Bd&use=n&k=2&b=911&n=1&d=1&VP=on&VC=on&EV=on&OD=on&PR=on&PRP=on&U=on&perpage=20&format=1&sent=Show[/URL]

[QUOTE=Stargate38;286099]It's the only prime of the for 2*911[sup]n[/sup]+1 that I've found, other than 1823. I used the factor tables.[/QUOTE]

Are you aware that factor tables is an inefficient search method and has the unfortunate side effect of queueing ALL of these numbers to be fully factored?

[URL="http://www.factordb.com/index.php?id=1100000000482633606"]2*911[sup]2171[/sup]+1[/URL] is prime (N-1).

Proth is faster. I just plug the prime numbers I find into the db when I find them.

[URL="http://factordb.com/index.php?id=1100000000294641741"]3^8890-2[/URL] needed the [URL="http://factordb.com/index.php?id=1100000000484273807"]p1402[/URL] from [URL="http://factordb.com/index.php?id=1000000000047128914"]3^8890-1[/URL] proven to complete an N+1 proof.

Although I don't know why there is interest in (3^3333+4), I enjoy finding cases like [URL="http://factorization.ath.cx/index.php?id=1100000000208024795"](3^3333+4)/31[/URL] in the PRP lists, where I can visually spot that N-1 has a difference of powers of 3 (3^3333-3^3) that leaves the cyclotomic number (3^3330-1). In many cases, including this one, helping the factordb find the algebraic factors of the cyclotomic number completes the primality proof.

Might be worth adding all the algebraic factorizations for cyclotomic numbers.

[QUOTE=henryzz;287450]Might be worth adding all the algebraic factorizations for cyclotomic numbers.[/QUOTE]

It's more complicated than that. The factordb already finds most of the algebraic factors for pure cyclotomic numbers. But it isn't capable of finding hidden cyclotomic numbers. This case was factoring (3^3333+4)/31-1. It would require a clever factoring process to automatically see this is (3^3330-1)*27/31, and therefore all the factors of 3^3330-1 except for 31 divide the number.

[QUOTE=wblipp;287433]Although I don't know why there is interest in (3^3333+4), I enjoy finding cases like [URL="http://factorization.ath.cx/index.php?id=1100000000208024795"](3^3333+4)/31[/URL] in the PRP lists, where I can visually spot that N-1 has a difference of powers of 3 (3^3333-3^3) that leaves the cyclotomic number (3^3330-1). In many cases, including this one, helping the factordb find the algebraic factors of the cyclotomic number completes the primality proof.[/QUOTE]While I can't speak on the [URL="http://www.mersenneforum.org/showthread.php?t=16438"]worth[/URL] of a particular number, I can point out a [URL="http://www.staff.amu.edu.pl/~florek/pnq/"]project[/URL] that worked on numbers with forms like this that had some considerable effort behind it. It looks like WsF never revived the project, but I was reminded of it by some work I had done that was sitting around in my files.....

[QUOTE=schickel;287489]I can point out a [URL="http://www.staff.amu.edu.pl/~florek/pnq/"]project[/URL] that worked on numbers with forms like this[/QUOTE]

It looks like the project has been inactive for a few years. If it were still active, it would be nice to have them update the factordb with their factors and primality proofs.

Browsing some some larger PRPs, I quickly found another one of these today. The proof was easily completed by helping the factordb find the algebraic factors of N+1. [URL="http://factorization.ath.cx/index.php?id=1100000000295456476"]14^2080+13[/URL]

I have helped many proofs like this.

I'm really hoping the database will get better at recognizing algebraic factors.

A very easy one: [URL="http://factordb.com/index.php?query=%285%5E3168-1%29*85%2F24%2B1"](5^3168-1)*85/24+1[/URL], [URL="http://factordb.com/index.php?query=%285%5E3168-1%29*85%2F24"]N-1[/URL] needed some factors from [URL="http://factordb.com/index.php?query=5%5E3168-1"]5^3168-1[/URL].

The same for [URL="http://factordb.com/index.php?id=1100000000490811958"](10^798-1)*970/99+1[/URL]: [URL="http://factordb.com/index.php?id=1100000000490811959"]N-1[/URL] needed help from [URL="http://factordb.com/index.php?id=1100000000020354583"]10^798-1[/URL]
and [URL="http://factordb.com/index.php?id=1100000000490831146"](5^1428-1)*85/24+1[/URL]: [URL="http://factordb.com/index.php?id=1100000000490831147"]N-1[/URL] needed help from [URL="http://factordb.com/index.php?id=1000000000047321452"]5^1428-1[/URL]
[URL="http://factordb.com/index.php?id=1100000000491185503"](2^3023+27)/5[/URL]: [URL="http://factordb.com/index.php?id=1100000000491189580"]N+1[/URL] needed help from [URL="http://factordb.com/index.php?id=1000000000012153042"]2^3018+1[/URL]
[URL="http://factordb.com/index.php?id=1100000000490812068"](16^564-1)*176/85+1[/URL]: [URL="http://factordb.com/index.php?id=1100000000491190753"]N-1[/URL] needed help from [URL="http://factordb.com/index.php?id=1000000000000002256"]2^2256-1[/URL]

[URL="http://factordb.com/index.php?id=1100000000315221110"](2^5354*75+1)/7[/URL]: uploading a primality certificate for [URL="http://factordb.com/index.php?id=1100000000348690578"]((2^5354*75+1)/7-1)/3018 [/URL]allowed an [URL="http://factordb.com/index.php?id=1100000000348690574"]N-1[/URL] proof.

Would it be possible to download all the prps with form (b^n+c)/d and similar forms? It should be possible to parse that sort of expression in a script such that the necessary factors of plus or minus one can be supplied.

[URL="http://factorization.ath.cx/index.php?query=%2810%5E1612*7-9%29%2F691"](10^1612*7-9)/691[/URL] [URL="http://factorization.ath.cx/index.php?id=1100000000271070305"]N-1[/URL] needed help from [URL="http://factorization.ath.cx/index.php?query=10%5E1610-1"]10^1610-1[/URL]

[URL="http://factorization.ath.cx/index.php?id=1100000000004642686"](10^1872*58+41)/99[/URL] needed help from 10^1872-1

8863^433-1 needed help with the factors of 8863^432-1.

There are many such numbers.

Once you have a list of the numbers the numbers of the form (b^n*k+-c)/d will be recognized by this in notepad++
^\(([0-9]+)\^([0-9]+)\*([0-9]+)([+-])([0-9]+)\)/([0-9]+)
I replaced these by:
correct (\1^\2*\3\4\5)/\6
Then I sort the lines in the file and remove those without correct at the beginning. Then I remove correct from the beggining of the lines.

Now I have a list of numbers which can be parsed and manipulated by a simple program.

Unfortunately show as plain text only works for composites so I can only manually copy 1000 at once and can't use a script to pull them. I have attached the results of the current first 1000 for people to browse more easily
A program finding which are possible should follow shortly.

Add $ to the end of
^\(([0-9]+)\^([0-9]+)\*([0-9]+)([+-])([0-9]+)\)/([0-9]+)
to make
^\(([0-9]+)\^([0-9]+)\*([0-9]+)([+-])([0-9]+)\)/([0-9]+)$

Otherwise it lets lines like
(13^1479*19-1)/453707218/3^9
(2^5438*45-1)/16775191/3461^2
through which confuse the program.

The results from running on the first 1000 prps
(10^1631*14-41)/99 -
(19^1274*11-1)/10 -
(19^1287*3+1)/2 +
(2^5463*77-1)/615 -
(2^5502*69-1)/275 -

(2^5502*69-1)/275 N-1 needed help with factors from 2^5500-1
This was the only one that benefitted as all the others had already been found but still don't have a large enough factored part.

Results upto 2000 digits:
[code](10^1631*14-41)/99 -
(10^1676*34-43)/3357 -
(10^1719*2+9)/7 -
(10^1728*52-43)/9 -
(10^1729*49-31)/459 -
(10^1730*23-11)/2289 -
(10^1770*62-71)/9 +
(10^1781*31-301)/9 -
(10^1786*43-421)/9 -
(10^1788*44-17)/27 -
(10^1791*5-17)/33 -
(10^1794*88-61)/27 -
(10^1801*52-529)/9 +
(10^1865*25-7)/2493 -
(10^1891*4-13)/27 -
(10^1902*7-691)/9 -
(10^1908*14-41)/27 +
(10^1937*22-1)/219 -
(10^1937*8-77)/3 -
(10^1944*26-23)/3 -
(10^1951*5-53)/3 +
(10^1978*35-341)/9 -
(11^1612*8-1)/967 -
(11^1662*3-1)/2 -
(17^1455*5-1)/24564 -
(17^1458*10-1)/9 -
(17^1472*19-1)/18 -
(17^1555*4+1)/3 +
(19^1274*11-1)/10 -
(19^1287*3+1)/2 +
(19^1409*10-1)/9 -
(2^5463*77-1)/615 -
(2^5521*129-1)/257 -
(2^5701*21+1)/83 +
(2^5948*173-1)/44287 -
(2^5991*61-1)/124927 -
(2^6062*45-1)/89 -
(2^6066*193-1)/771 -
(2^6139*11-1)/21 -
(2^6140*17-1)/67 -
(2^6295*91-1)/727 -
(2^6394*85-1)/1359 -
(2^6481*105-1)/209 -
(2^6553*59-1)/117 -
(2^6557*113-1)/3615 -
(663^663*3+1)/2 +
[/code]
I haven't checked these. Done enough for this evening.
If someone can provide a bigger list of prps I can check them easily. Soon I will add more forms to my program.

(10^1728*52-43)/9 done

Great work! Sure beats my manual scans.

(2^6481*105-1)/209 - finished.

done a few more

Everything base 10 is done long ago at M.Kamada's site. It only needs to be imported.

Nice work henryzz. Done [URL="http://factordb.com/index.php?id=1100000000378709592"]N-1[/URL] proof for [URL="http://factordb.com/index.php?id=1100000000367876168"](2^6140*17-1)/67[/URL].

Worth checking these prps found while trying to prove prps:
[code](((12^60+1)^2-2)*(11^1531-1)+1)/30943899
(((12^60+1)^2-2)*(11^1661-1)+1)/2847
(((12^60+1)^2-2)*(11^1737-1)+1)/3247287
(((12^60+1)^2-2)*(7^1904+1)+1)/88320845
(((12^60+1)^2-2)*(7^2056+1)+1)/55
(((419#-8675309)*10^282+1)*10^1174-1)/535549
((107^983+1)/108+1)/382908
((10^1632*394-7)/9-1)/5031247566694608
((10^1667*4-3)/2329249+1)/29708213026
((10^1699*17-53)/20943-1)/4
((10^1709*106+17)/3-1)/82
((10^1716*19-1)/773757+1)/94740004
((10^1727*46-1)/9-1)/82223670
((10^1731-1)*911/999+10^1731)/273
((10^1742*5+31)/1262187+1)/6534662
((10^1746*83-101)/9+1)/423284
((10^1841*79-7)/340407-1)/233854
((10^1864*5-41)/790401339-1)/57980
((10^1872*46+53)/4257-1)/33293740741674252
((10^1907*52-43)/2825054631+1)/95743456284
((10^1930-1)/3+10^1930*410)/10186163
((10^1938*403-43)/9-1)/268450910052
((10^1992*53-791)/9+1)/9009246
((117^919+919^117)/423628-1)/5590446
((12^911+1)^2-2)/23602615806575407
((139^794+794^139)/18945-1)/259177880
((17239^449-1)/17238+1)/6
((17^1395*5-1)/635752046508-1)/92014
((17^1438*20+1)/1098987-1)/451778
((17^1505*15-1)/2586395157739267814-1)/60
((17^1562*3-1)/47296782852070432918+1)/204
((2^5480*125-1)/15469-1)/112001010
((2^5592*183+1)/1017756034007+1)/1802064888
((2^5631*161+1)/21614858257-1)/27434096
((2^5696*137+1)/2116071-1)/3258302
((2^5730*183+1)/9910277767-1)/36237714
((2^5761*199+1)/2193303-1)/978
((2^5835*73-1)/670391-1)/32726264
((2^5902*69+1)/73-1)/85211832
((2^5930*193-1)/6956802429+1)/1580
((2^5964*127-1)/26916772743-1)/232
((2^6055*9-1)/1290060103-1)/588015508808
((2^6056*95+1)/259775367-1)/7092334
((2^6090*57-1)/203+1)/41630
((2^6151*63-1)/49803415643-1)/2241780
((2^6258*59-1)/2585+1)/86156391432
((2^6338*43-1)/11320285671+1)/3918
((2^6369*145+1)/8522863594867449+1)/190
((2^6392*6393-1)/22625351+1)/28562375086
((2^6498*115+1)/2299846117+1)/125834733726
((2^6579*147-1)/10585-1)/1490
((2^6591*6590-1)/3173061-1)/88416238702
((2^6616*11-1)/35+1)/18978
((3^2424*2^2423)^1+1)/11
((3^2492*2^2491)^1+1)/4409
((40^1148+1148^40)/2^80/105649+1)/3572330250
((555^701-701^555)*2-1)/379916187233
((6^2150-1)*2/5+3)/14879
((6^2152-1)*2/5+3)/139
((6^2157-1)*2/5+3)/257611
((6^2159-1)*2/5+3)/435443
((709^683-1)/488400348-1)/8278314231120
((798^593-1)/797+1)/482578228 [/code]These are a bit too complex and few in number to be worth modifying my program for.

Here are numbers to check when k and/or d are 1:
[code](10^1796*1-97)/3 -
(1153^563*1-1)/1152 -
(11^1589*1+10)/111 +
(11^1907*1-1)/10 -
(12739^449*1-1)/12738 -
(14969^449*1-1)/14968 -
(1531^593*1-1)/1530 -
(17239^449*1-1)/17238 -
(20^1487*1-1)/19 -
(2241^127*1-1)/2240 -
(2285^127*1-1)/2284 -
(2324^127*1-1)/2323 -
(271^709*1-1)/270 -
(3079^463*1-1)/3078 -
(3352403^257*1-1)/3352402 -
(3461^479*1-1)/3460 -
(3919^499*1-1)/3918 -
(3^4033*1+2)/25 +
(3^4153*1+2)/25 +
(4451^463*1-1)/4450 -
(4801^439*1-1)/4800 -
(4801^463*1-1)/4800 -
(4831^487*1-1)/4830 -
(500^683*1-1)/499 -
(5657^457*1-1)/5656 -
(5689^439*1-1)/5688 -
(6011^499*1-1)/6010 -
(605^605*1+604)/365421 +
(6121^443*1-1)/6120 -
(6173^467*1-1)/6172 -
(6197^439*1-1)/6196 -
(644^613*1-1)/643 -
(665^631*1-1)/664 -
(6^2496*1-11)/5 +
(705669073^223*1-1)/705669072 -
(7213^461*1-1)/7212 -
(7307^479*1-1)/7306 -
(732^661*1-1)/731 -
(8059^431*1-1)/8058 -
(853^619*1-1)/852 -
(902^563*1-1)/901 -
(9491^479*1-1)/9490 -
(9587^457*1-1)/9586 -
(19^1422*1+18)/1 +
(22^1248*1+21)/1 +
(23^1390*1+22)/1 +
(24^1194*1-23)/1 -
(24^1404*1-23)/1 -
(28^1279*1+27)/1 +
(2^5392*1+63)/1 +
(2^5484*1+63)/1 +
(2^5517*1-63)/1 -
(2^5547*1+3)/1 -
(2^5547*1+3)/1 +
(2^5567*1+9)/1 -
(2^5586*1-17)/1 +
(2^5588*1+127)/1 +
(2^5607*1+65)/1 -
(2^5678*1-33)/1 +
(2^5742*1+255)/1 +
(2^5904*1-17)/1 +
(2^5955*1+255)/1 +
(2^6017*1-15)/1 -
(2^6136*1-63)/1 -
(2^6147*1+1025)/1 -
(2^6174*1+2049)/1 -
(2^6338*1-33)/1 +
(2^6437*1-31)/1 -
(2^6465*1+1025)/1 -
(2^6495*1+8193)/1 -
(30^1155*1+29)/1 +
(31^1230*1+30)/1 +
(34^1174*1-33)/1 -
(39^1187*1-38)/1 -
(39^1197*1-38)/1 -
(43^1017*1-42)/1 -
(45^1172*1+44)/1 +
(46^1166*1+45)/1 +
(48^1114*1+47)/1 +
(49^1076*1+48)/1 +
(52^939*1+51)/1 +
(69^1034*1+68)/1 +
(70^1021*1-69)/1 -
(70^1030*1+69)/1 +
(72^1054*1-71)/1 -
(605^605*3+2)/1 +
[/code]I cover about 80% of prps in short form below 2000 digits.

Can many numbers of the form (x^y*y^x+-f)/d be helped? I believe I could process them but would hardly get any useful results as we don't have factorizations of x^a*y^b+-1. They are about 10% of the total numbers.

I make regex's for some more forms and the last 5% is pretty much rare stuff.
I have attached my list of prps sorted with the forms marked. I can only process forms 1-3.5

What have people checked from the numbers I posted? I can check some more tomorrow.

[QUOTE=henryzz;291469]What have people checked from the numbers I posted? I can check some more tomorrow.[/QUOTE]
I have proven many of the numbers you've posted.

Not many in the last file, yet.

(11^1724*5+1)/6-1 need help with (11^431*3+3)/1516829834365402334277715308 or (11^862*3+3)/992082412380769750967560817656886431636998
(10^1627*14+13)/603+1 need (10^1625*25+11)/4141336702683390924663927819 factors
(10^1631*14-41)/99-1 need help with either(10^815+1)/(10^163+1) or(10^815-1)/(10^163-1)
(2^5358*175-1)/111-1) need help with (2^2677*5+1)/23300488449386234700116099
((2^5434*135+1)/79+1) need help with (2^1810*3+1)/1115755075968493924957
(2^5440*177+1)/591329-1 is FF but has a PRP1615 (proded, no luck)
((10^1731-1)*911/999+10^1731)/273-1 is FF but has a PRP1715(proded, no luck)
((10^1742*5+31)/1262187+1)/6534662+1 is FF, PRP1725 (proded, no luck)
((10^1841*79-7)/340407-1)/233854+1 is FF PRP1825 (proded, no luck)

and I poked a number of other (mainly 8-20 digits prime)

[B]Test finished![/B]
[B]PFGW output:[/B]

Primality testing (11^2577-1)/(11^859-1)/133 [N-1, Brillhart-Lehmer-Selfridge]
Prime_Testing_Warning, unused factor from helper file: 61 Prime_Testing_Warning, unused factor from helper file: 826129 Running N-1 test using base 7
Calling Brillhart-Lehmer-Selfridge with factored part 33.44% (11^2577-1)/(11^859-1)/133 is prime! (0.2408s+0.0001s)Proven by combined N+1/N-1-method

Henry,

I think the provable primes from your lists have been proven. But I see there are still easy pickings for higher numbers. I jacked the digit count up and scanned less than 200 PRPs before spotting [URL="http://factorization.ath.cx/index.php?id=1100000000315350692"](2^10069*19+1)/39[/URL]. Are you going to extend your search to higher PRPs?

And just below it was [URL="http://factorization.ath.cx/index.php?id=1100000000291740572"](10^3031*35-359)/9[/URL]

[QUOTE=wblipp;291808]I think the provable primes from your lists have been proven.[/QUOTE]

Double checking, I found some in the first list that could still be completed. I believe these really are as complete as possible with algebraic factors and the known factordb results. I haven't double checked the other lists yet.

Some 3 for 1 opportunities gleaned from Henry's Post #75. A Primo proof of the first number will enable a N+/-1 proof of the second number which will enable an N+/-1 proof of the third number.

[URL="http://factorization.ath.cx/index.php?id=1100000000491664220"](((2^6616*11-1)/35+1)/18978-1)/218489095992628142393749204529429310[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000378751554"]((2^6616*11-1)/35+1)/18978[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000362737724"](2^6616*11-1)/35[/URL]

[URL="http://factorization.ath.cx/index.php?id=1100000000460876206"](((10^1841*79-7)/340407-1)/233854+1)/12767374[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000426709209"]((10^1841*79-7)/340407-1)/233854[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000000756898"](10^1841*79-7)/340407[/URL]

[URL="http://factorization.ath.cx/index.php?id=1100000000441718576"](((10^1742*5+31)/1262187+1)/6534662+1)/423806[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000426685941"]((10^1742*5+31)/1262187+1)/6534662[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000000811390"](10^1742*5+31)/1262187[/URL]


This came from the same source, but I cannot find a third prime in the chain:
[URL="http://factorization.ath.cx/index.php?id=1100000000438688459"](((10^1731-1)*911/999+10^1731)/273-1)/107767440900618[/URL]
[URL="http://factorization.ath.cx/index.php?id=1100000000412150747"]((10^1731-1)*911/999+10^1731)/273[/URL]

Edwin Hall uploaded a certificate for a prp1139 that emerged from (9636^1093-1)/9635-1. This allowed me to prove a p4351.

I've been adding several such numbers lately. The one closest to a proof is (5995^1009-1)/5994. N-1 is 32.79% factored.

I don't think these are proven before, since the [base]>[5*the exponent].

[QUOTE=lorgix;291896]The one closest to a proof is (5995^1009-1)/5994. N-1 is 32.79% factored.
[/QUOTE]
Use Konyagin-Pomerance test with >30% factored, and the C-H-G method all the way down to 26.0% (and a bit below).

The fun part is doing Konyagin-Pomerance test from scratch. The PN-ACP book has its description, it's short and sweet. Or you can get existing recipes from the yahoo primeform discussion group - but this is less fun.

I might search higher digits. Downloading the numbers in pages of 1000 gets tedious quickly.
If someone provides me with the list of prps then I can put virtually any amount through my program.

factordb can give you the entire list of prp, if you click the right link...

[QUOTE=firejuggler;292038]factordb can give you the entire list of prp, if you click the right link...[/QUOTE]
Whoops!! Didn't reallize it was in downloads. Will do it now.

2283/52114 prps of the supported forms are provable. I have attached them. This includes those already posted.
It would also be worth sorting the prps file and finding cases like wblipp was showing earlier. I am afraid I have a much better example:
[CODE](((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((10^5503*8-77)/3+1)/312349533226-1)/26056407916324+1)/12068077670-1)/7671531812395018986+1)/48645809022+1)/2674683565110+1)/7562064497826-1)/41769654987102-1)/11440636416+1)/70253722+1)/533955009545772+1)/12297239861360496410+1)/9622227016-1)/9013878514535854+1)/698-1)/52959618503662848-1)/31569336+1)/160976751926158016210408098+1)/74966617284-1)/109706013282900-1)/176847982314+1)/55121810496642422658+1)/8514+1)/191350974648-1)/23748875200832304+1)/75592+1)/40640768535349418231106378-1)/1229520+1)/12506-1)/22803169324306304931762-1)/1140+1)/6239780654350487136508+1)/4009600720608-1)/2616637312-1)/698158170+1)/11215615512236595900-1)/533133494+1)/2493425220-1)/1331913532188030+1)/525498414647425108+1)/35443023556040827138602-1)/17544-1)/6243604968-1)/201496166684410-1)/892790980836582-1)/1522242561714-1)/4507185012312+1)/572094144+1)/81892177151041245387894+1)/1781071972+1)/714769719120786-1)/10973071283412+1)/192544187996-1)/42-1)/32599018970484-1)/368437910072585738822105164-1)/230897064-1)/29056470676756209944126974512+1)/4426147918641991802658102+1)/1684724+1)/2897121485643118-1)/5455141008932059690-1)/16194155326266-1)/357930-1)/213155742656064-1)/567696427221042+1)/8829083949259207565816+1)/360458374328-1)/5595698854461654840-1)/47222075735894+1)/16950527447280+1)/2099576309007702+1)/122224775328439722102-1)/1312437577918858-1)/69254820+1)/41242926-1)/313138306+1)/24799786442+1)/3445984429639960+1)/1243137060674389404+1)/41239668-1)/69318866014621281543825019940+1)/87909163931622487806+1)/16478737570-1)/599510225102930182+1)/11826580522-1)/23468042-1)/3195827900174218+1)/12107142751540-1)/157962960563471516-1)/335842+1)/9392693066672920018+1)/1102123708877820+1)/20694421620+1)/58490586688947393957582-1)/1147270958-1)/2105007715065470-1)/7090-1)/19202836278+1)/600272899951426+1)/413031144-1)/42554453341370890+1)/448201499883294100527893740-1)/526578798998-1)/32502561634016762-1)/825828294471260587738-1)/511842-1)/456691916158912+1)/5621535740854434834105400-1)/114158594+1)/229264833825277014+1)/1673126+1)/355746876527654+1)/21830834615032001333813906+1)/405104+1)/44388107144+1)/49092340640258-1)/215700-1)/52880920162+1)/3881806377874463816-1)/41152793082490752-1)/7481468123929735708807038+1)/289828632+1)/2828299730012+1)/7431655432530364+1)/117445499149789236+1)/514105500+1)/853849723628+1)/83145222885020-1)/7556996592090+1)/14251281591262174322510+1)/23248784-1)/2531945029410-1)/2176+1)/120435697186954834256762-1)/312405045591127290-1)/71111847100856+1)/12966+1)/1344558-1)/173449389583869334354-1)/4580360029162572+1)/135006[/CODE]This is 143 deep!!! Other paths have obviously been tried as well. Someone was really persistent with this one. Also (18007094922^206-1)/189427607104473963157 has been tried a lot.

[QUOTE=henryzz;292044]This is 143 deep!!![/QUOTE]

I don't think it generates a chain of primes. Many of the numbers are composite+1 or composite-1, not prime+1 or prime-1. It looks like somebody just chained on the largest factor, regardless of prime of composite.

Just finished (5830^1093-1)/5829, I think I got some help with a factor of N-1.

I also proved (6746^1171-1)/6745. N-1 had a prp1074 that I didn't even need to prove.

[QUOTE=lorgix;292229]Just finished (5830^1093-1)/5829, I think I got some help with a factor of N-1.

I also proved (6746^1171-1)/6745. N-1 had a prp1074 that I didn't even need to prove.[/QUOTE]
Yes you did, otherwise you cannot claim the proof of (6746^1171-1)/6745. The DB (and PFGW behind it) tells you that this PRP is P conditional on all known P factors. The fact that the DB takes PRPs into the helper file is a bug (or you can call it a feature).

[QUOTE=Batalov;292231]Yes you did, otherwise you cannot claim the proof of (6746^1171-1)/6745. The DB (and PFGW behind it) tells you that this PRP is P conditional on all known P factors. The fact that the DB takes PRPs into the helper file is a bug (or you can call it a feature).[/QUOTE]
I meant that the other factors, known Ps, were enough. I don't think the prp1074 was used.

Yes, you are right, there's just enough without it! Grocery bill paradox got me (the factors looked shorter than the whole bill).
Sorry!

(10^2018*58-31)/5769 proved by N-1
11^2185-10 proved by N-1

[URL="http://www.factordb.com/index.php?id=1100000000453204369"]49^1765-48[/URL], needed factors from [URL="http://www.factordb.com/index.php?id=1000000000047523552"]7^3528-1[/URL] for the [URL="http://www.factordb.com/index.php?id=1100000000461340294"]N-1[/URL] proof.

[URL="http://factordb.com/index.php?id=1100000000014382840"](10^5040*34-7)/27[/URL], [URL="http://factordb.com/index.php?id=1100000000271896456"]N-1[/URL] proof done.