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

 2015-04-02, 17:27 #243 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23DF16 Posts 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. Last fiddled with by Batalov on 2015-04-02 at 17:34 Reason: typos, footnote
 2015-04-03, 15:02 #244 chris2be8     Sep 2009 194810 Posts Continuing my search for PRPs with factorable N+1 or N-1 I've found http://factorization.ath.cx/index.ph...00000635654313, (10^1000+25739)^10*10+1, where N-1 has a large PRP factor http://factorization.ath.cx/index.ph...00000746266343 to the 10th power. So proving it will make N-1 fully factored. Chris
 2015-04-04, 15:40 #245 chris2be8     Sep 2009 22×487 Posts @Batalov, thanks for that, so I didn't miss anything significant. So need not waste time looking for something that's not there. Chris
 2015-04-05, 19:59 #246 chris2be8     Sep 2009 79C16 Posts And another like the last one: Proving http://factorization.ath.cx/index.ph...00000772489376 (1007 digits) will enable a N-1 proof for http://factorization.ath.cx/index.ph...00000635678150, (10^1015+38358)^10*10+1 (10152 digits). Chris
 2015-04-07, 17:09 #247 chris2be8     Sep 2009 111100111002 Posts 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 http://factorization.ath.cx/index.ph...00000772818863 (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
2015-04-07, 19:04   #248
Wick

Nov 2012

23·32 Posts

Quote:
 Originally Posted by chris2be8 After adding algebraic factors (2^34861*39-1)/77-1 (10494digits) is now 22.099% factored, and it also has one large PRP http://factorization.ath.cx/index.ph...00000772818863 (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
It was enough to prove.

2015-04-07, 19:33   #249
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts

Quote:
 Originally Posted by chris2be8 After adding algebraic factors (2^34861*39-1)/77-1 (10494digits) is now 22.099% factored, and it also has one large PRP http://factorization.ath.cx/index.ph...00000772818863 (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:
 Originally Posted by Wick It was enough to prove.
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
# or
additional_prime = 1180 + log10(.350655876) # the length plus log10([dot]the starting digits of the long number)
print(new_factored_ratio/whole_number)
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.

Last fiddled with by Mini-Geek on 2015-04-07 at 19:41

 2015-04-08, 16:00 #250 chris2be8     Sep 2009 36348 Posts 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
2015-04-08, 18:03   #251
wblipp

"William"
May 2003
New Haven

23×5×59 Posts

Quote:
 Originally Posted by chris2be8 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?
Syd didn't write his own testing code - he uses PFGW. You probably need to get the upgrade done there.

 2015-04-08, 18:05 #252 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 217378 Posts 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).
2015-04-08, 18:13   #253
paulunderwood

Sep 2002
Database er0rr

5×701 Posts

Quote:
 Originally Posted by Batalov (i.e. for 30% ... 1/3 factored N^2-1)
I have made that mistake before: since we are factoring N^2-1 it should be 15%...1/6

 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 06:41.

Sat Dec 5 06:41:29 UTC 2020 up 2 days, 2:52, 0 users, load averages: 1.38, 1.39, 1.46