D.Broadhurst undoubtedly has tabulated all of those that hold promise of a KP or a CHG proof* as long ago as a decade ago, so all easy ones are done! The usual contributors in this particular class are Chuck Lasher, Bouk de Water and David himself. PRPtop has some PRP leads and I've recently added some by PRP-scanning primU/V()'s up to n<400,000. Note: for prime N, primU() = simply Fib() and primV() = simply lucas(), so these were known for years (and found by Lifchitz).

Note: D.Broadhurst also maintains the ad hoc reservation for the "algebraically hopeless" primU/V()'s, so if you would be thinking about running Primo on one, you will do well by first reserving it. (I didn't know that, but now I do, and I spread the word.)

_______________
*That promise is in factoring at least some of the composites in the N-1 or N+1 factorization. See primU(137439)-1 cofactors; they can yield to ECM or in some cases NFS; also note that for some of them mersennus.net/fibonacci may have a better factorization that was at some time imported into FactorDB.

Continuing my search for PRPs with factorable N+1 or N-1 I've found [url]http://factorization.ath.cx/index.php?id=1100000000635654313[/url], (10^1000+25739)^10*10+1, where N-1 has a large PRP factor [url]http://factorization.ath.cx/index.php?id=1100000000746266343[/url] to the 10th power. So proving it will make N-1 fully factored.

Chris

@Batalov, thanks for that, so I didn't miss anything significant. So need not waste time looking for something that's not there.

Chris

And another like the last one:

Proving [url]http://factorization.ath.cx/index.php?id=1100000000772489376[/url] (1007 digits) will enable a N-1 proof for [url]http://factorization.ath.cx/index.php?id=1100000000635678150[/url], (10^1015+38358)^10*10+1 (10152 digits).

Chris

So near and yet so far.
 

After adding algebraic factors (2^34861*39-1)/77-1 (10494digits) is now 22.099% factored, and it also has one large PRP [url]http://factorization.ath.cx/index.php?id=1100000000772818863[/url] (1180 digits). Which is not quite enough for factordb to prove (2^34861*39-1)/77 prime.

And no other composite factors are small enough to be worth trying to factor. It's 2^34860-1 after removing small factors so probably has had enough ECM etc run against it's factors that finding another factor would take more work that proving (2^34861*39-1)/77 prime with PRIMO.

Chris

[QUOTE=chris2be8;399552]After adding algebraic factors (2^34861*39-1)/77-1 (10494digits) is now 22.099% factored, and it also has one large PRP [URL]http://factorization.ath.cx/index.php?id=1100000000772818863[/URL] (1180 digits). Which is not quite enough for factordb to prove (2^34861*39-1)/77 prime.

And no other composite factors are small enough to be worth trying to factor. It's 2^34860-1 after removing small factors so probably has had enough ECM etc run against it's factors that finding another factor would take more work that proving (2^34861*39-1)/77 prime with PRIMO.

Chris[/QUOTE]

It was enough to prove.

[QUOTE=chris2be8;399552]After adding algebraic factors (2^34861*39-1)/77-1 (10494digits) is now 22.099% factored, and it also has one large PRP [url]http://factorization.ath.cx/index.php?id=1100000000772818863[/url] (1180 digits). Which is not quite enough for factordb to prove (2^34861*39-1)/77 prime.

And no other composite factors are small enough to be worth trying to factor. It's 2^34860-1 after removing small factors so probably has had enough ECM etc run against it's factors that finding another factor would take more work that proving (2^34861*39-1)/77 prime with PRIMO.

Chris[/QUOTE]

[QUOTE=Wick;399559]It was enough to prove.[/QUOTE]

You can always tell something like this in advance, using multiplying/dividing (logarithms and antilogarithms can make this easier) to determine if it will have >1/3 factored. In this example, using Python:

[CODE]from math import log10
whole_number = log10((2**34861*39-1)//77-1)
factored_ratio = whole_number * 0.22099
additional_prime = log10(3506558761926971512477297296683018240237802676731644055250045204537775194400010178087998447321507478600817592705616161405817738352734894144721317929263324912197266117511551580761732541869669876689987165726621178684600171482007104597962677886695675167576338925575553986046610303368144884568916407098842880063824741179033940355870192625557343740123589410849730577079283148102933868035818491353137898013930244384291688588275054632147751736981106084248913391524320601903576237544952769251891260207999716952903190778749065796352828097883738968079636783614385584428272648346785025793447800638665413535803201979495988829833362404777758623082617387265333067529872148141192233553075004206944147802358620404080736497689698476221395097842352160492710593555790826888291012451038050049824479137168165964693849277060186810651364706931928084605931133410403663856663152305108447186454974035882713078010346173759344206193326603356739063396771113048615128471201410957739917292042987815135728382012015386609272490787328671741261167085118548057393212461278670329195501025353396663783059566063839318304945626306880713050813110162727173939454863315799108485675073025126029693463381547229527938485439361)
# or
additional_prime = 1180 + log10(.350655876) # the length plus log10([dot]the starting digits of the long number)
new_factored_ratio = additional_prime + factored_ratio
print(new_factored_ratio/whole_number)[/CODE]
the result is 0.33339..., or 33.339%, just barely large enough to enable the primality test. If it came any closer, the "22.099%" figure wouldn't be accurate enough to tell, and you'd have to multiply out the known primes (FactorDB's helper file function could help here) to get the exact figure.

OK, Thanks for proving it. I'll make a note that the limit's exactly 33.3333% factored.

So using bc I could have done:
1180*100/10494+22.099
33.343

But there are a lot of numbers with N+1 or N-1 between 25% and 33.333% factored. @syd, could you please upgrade the test to work in this case?

Chris

[QUOTE=chris2be8;399639]But there are a lot of numbers with N+1 or N-1 between 25% and 33.333% factored. @syd, could you please upgrade the test to work in this case?[/QUOTE]

Syd didn't write his own testing code - he uses PFGW. You probably need to get the upgrade done there.

Running K-P tests (i.e. for 30% ... 1/3 factored N^2-1) would be easy to set up; this is just a fairly simple sequence of scripts, but ~28% ...30% will have difficulty running unattended, and some of them may be quite long. Some of the tougher test (~26% ...28% CHG) may run for a very, very, very long time. Not a robust idea on a server.

There is a straightforward K-P implementation as a GP script on top of the usual PFGW test (which will run and report PRP with 90%+ proof).

[QUOTE=Batalov;399655](i.e. for 30% ... 1/3 factored N^2-1) [/QUOTE]

I have made that mistake before: since we are factoring N^2-1 it should be 15%...1/6 :geek: