mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2015-04-02, 17:27   #243
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23DF16 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2015-04-03, 15:02   #244
chris2be8
 
chris2be8's Avatar
 
Sep 2009

194810 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2015-04-04, 15:40   #245
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22×487 Posts
Default

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

Chris
chris2be8 is offline   Reply With Quote
Old 2015-04-05, 19:59   #246
chris2be8
 
chris2be8's Avatar
 
Sep 2009

79C16 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2015-04-07, 17:09   #247
chris2be8
 
chris2be8's Avatar
 
Sep 2009

111100111002 Posts
Default 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
chris2be8 is offline   Reply With Quote
Old 2015-04-07, 19:04   #248
Wick
 
Nov 2012

23·32 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
Wick is offline   Reply With Quote
Old 2015-04-07, 19:33   #249
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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 View Post
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
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)
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
Mini-Geek is offline   Reply With Quote
Old 2015-04-08, 16:00   #250
chris2be8
 
chris2be8's Avatar
 
Sep 2009

36348 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2015-04-08, 18:03   #251
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
wblipp is offline   Reply With Quote
Old 2015-04-08, 18:05   #252
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217378 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2015-04-08, 18:13   #253
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by Batalov View Post
(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
paulunderwood 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 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

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.