mersenneforum.org > Math Crandall/Pomerance/Euler series question?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-19, 03:16 #1 grandpascorpion     Jan 2005 Transdniestr 503 Posts Crandall/Pomerance/Euler series question? Hello, In "Prime Numbers: A Computational Perspective", there's a question whether a series will eventually cover all the prime numbers. Starting with 2. Add 1 to your product of primes, factor that number, use the low prime factor. Repeat. Here's the resulting series: 2 3 7 43 13 53 5 6221671 38709183810571 ... 4357 (last in known list) From what I've seen it's stuck on the 43rd term, a 180 digit number known to be composite. Does anyone know if this nut has been cracked? I'm interested in factoring it and wouldn't want to duplicate previous work. Forgive me if there's another name for this series. In addition, I'm curious if anyone has looked at different branches (if you will) of the factor sequence. For instance, we have 2 * 3 * 7 * 43 +1 = 1807 = 13 * 139. Instead of taking the 13 "low branch", take 139 and see what progress can be made there. 2 3 7 43 139* 5 233 6079 457 ... Thanks, Grandpa Last fiddled with by grandpascorpion on 2005-01-19 at 03:18
 2005-01-19, 04:34 #2 wblipp     "William" May 2003 New Haven 94116 Posts http://www.research.att.com/cgi-bin/...i?Anum=A000945 http://www.research.att.com/cgi-bin/...i?Anum=A000946 Looks like no recent progress on either series.
 2005-01-19, 04:50 #3 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 111910 Posts Post that 180-digit composite here, and I will bet that you will find some people interested in trying to factor it. At some point, we may reach the point where we find the smallest factor of the next product+1 by ECM but cannot rigorously prove that the factor is actually the smallest.
 2005-01-20, 04:21 #4 grandpascorpion     Jan 2005 Transdniestr 503 Posts Thanks for the feedback. Here's the expression: 2 * 3 * 7 * 43 * 13 * 53 * 5 * 6221671 * 38709183810571 * 139 * 2801 * 11 * 17 * 5471 * 52662739 * 23003 * 30693651606209 * 37 * 1741 * 1313797957 * 887 * 71 * 7127 * 109 * 23 * 97 * 159227 * 643679794963466223081509857 * 103 * 1079990819 * 9539 * 3143065813 * 29 * 3847 * 89 * 19 * 577 * 223 * 139703 * 457 * 9649 * 61 * 4357+ 1 The number is: 2784908410762794071887414394815651793559267258537102016323316206429820623899017418905799635244237826374359490416665 25000702723914662388812510545494307250950777886431051612811386531 For the past 36 hours, I have been trying to factor this at http://www.alpertron.com.ar/ECM.HTM Current stats: Limit: B1=1000000, B2=100000000 Curve 328 Digits in factor: > 15 100%; > 20, 100%; > 25, 86%; > 30, 15%; > 35, 2%, > 40, 0 mod mult: 329384000 Step1: 46% I'm still a newbie to this. As great as it is, it's a Java applet. Perhaps, someone could recommend a different tack or a way to optimize using the applet. Thanks
2005-01-20, 09:15   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3×5×743 Posts

Quote:
 Originally Posted by philmoore Post that 180-digit composite here, and I will bet that you will find some people interested in trying to factor it. At some point, we may reach the point where we find the smallest factor of the next product+1 by ECM but cannot rigorously prove that the factor is actually the smallest.
There is good reason to believe that this number will be factored soon --- in the next five years or so.

There are two cases to consider: the smallest factor is small, under 50 digits or so, or that it is not. If the former, a concerted ECM attack should find it and the co-factor, if not prime, will be relatively easy by GNFS. If the smaller factor is too large, the entire number is just about within reach of GNFS now. The current record is RSA-576 which has 174 digits, if I remember correctly. That's only 6 digits short of the case in question.

Paul

 2005-01-20, 09:44 #6 garo     Aug 2002 Termonfeckin, IE 1010110011012 Posts grandpascorpion, Try using GMP-ECM. It will be much faster than the applet. It is available from Paul Zimmerman's page - just do a google search. Mind you, you need GMp-ECM and not the ECMNET extension. Also, read up Paul Z.'s main page. It will give you information on what bounds to use and what number of factors to run. From the information you posted about the curves you have already run, it would make sense to start the effort at 30 digits. Also, there are a couple of threads in the factoring forum that talk about running GMP-ECM, so reading them will also be useful.
 2005-01-20, 12:24 #7 grandpascorpion     Jan 2005 Transdniestr 503 Posts Thanks, will do.
 2005-01-20, 13:51 #8 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 101000000011102 Posts Using the applet I have run curves number 800-850.
2005-01-20, 14:49   #9
Xyzzy

Aug 2002

100000110110002 Posts

I've done up through 35 digits (1e6)... We can probably coordinate to do 40 digits very quickly...
Attached Files
 ecm.out.gz (26.5 KB, 129 views)

 2005-01-20, 14:56 #10 grandpascorpion     Jan 2005 Transdniestr 503 Posts Sorry another newbie question ... say I pick B1=3000000 (the opt value for a 40 digit factor) and B2=B1*100, is there a chance a smaller factor (say 25 digits) could be missed? (I think Phil Moore may have alluded to this earlier in the thread) Thanks, Grandpa
2005-01-20, 15:04   #11
Xyzzy

Aug 2002

840810 Posts

Quote:
 Originally Posted by grandpascorpion Sorry another newbie question ... say I pick B1=3000000 (the opt value for a 40 digit factor) and B2=B1*100, is there a chance a smaller factor (say 25 digits) could be missed? (I think Phil Moore may have alluded to this earlier in the thread)
In my (limited) experience, if there is a smaller factor it will be found, if you run enough curves... I think the advantage to running the more curves to a smaller bound is you get a greater statistical chance of getting a "winning" sigma value...

Since I've done up to 35 digits entirely any further work needs to be done at 40 digits, so your B1 should be 3e6...

On my K8, with a heavy load, it looks like I can do one curve every 75s or so... So 2900 curves should take about 60h... I plan to run a few other ECM jobs at the same time, so it will take much longer though... The good news is we can all split up the work...

Code:
GMP-ECM 5.0.3 [powered by GMP 4.1.4] [ECM]
Input number is 278490841076279407188741439481565179355926725853710201632331620642982062389901741890579963524423782637435949041666525000702723914662388812510545494307250950777886431051612811386531 (180 digits)
Using B1=3000000, B2=4016636514, polynomial Dickson(12), sigma=4291087327
Step 1 took 38399ms
Step 2 took 36153ms

 Similar Threads Thread Thread Starter Forum Replies Last Post YuL Math 3 2017-06-02 10:51 sean Factoring 2 2006-10-23 21:08 Barry Fagin Math 2 2006-01-04 19:46 Numbers Math 16 2005-10-16 00:53 Orgasmic Troll Math 1 2004-09-13 19:01

All times are UTC. The time now is 19:31.

Wed Jan 26 19:31:06 UTC 2022 up 187 days, 14 hrs, 0 users, load averages: 1.19, 1.21, 1.21