20050119, 03:16  #1 
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 20050119 at 03:18 
20050119, 04:34  #2 
"William"
May 2003
New Haven
941_{16} Posts 
http://www.research.att.com/cgibin/...i?Anum=A000945
http://www.research.att.com/cgibin/...i?Anum=A000946 Looks like no recent progress on either series. 
20050119, 04:50  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
Post that 180digit 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.

20050120, 04:21  #4 
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 
20050120, 09:15  #5  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
3×5×743 Posts 
Quote:
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 cofactor, 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 RSA576 which has 174 digits, if I remember correctly. That's only 6 digits short of the case in question. Paul 

20050120, 09:44  #6 
Aug 2002
Termonfeckin, IE
101011001101_{2} Posts 
grandpascorpion,
Try using GMPECM. 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 GMpECM 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 GMPECM, so reading them will also be useful. 
20050120, 12:24  #7 
Jan 2005
Transdniestr
503 Posts 
Thanks, will do.

20050120, 13:51  #8 
6809 > 6502
"""""""""""""""""""
Aug 2003
101ร103 Posts
10100000001110_{2} Posts 
Using the applet I have run curves number 800850.

20050120, 14:49  #9 
Aug 2002
10000011011000_{2} Posts 
I've done up through 35 digits (1e6)... We can probably coordinate to do 40 digits very quickly...

20050120, 14:56  #10 
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 
20050120, 15:04  #11  
Aug 2002
8408_{10} Posts 
Quote:
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:
GMPECM 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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Carl Pomerance himself about 210  YuL  Math  3  20170602 10:51 
Exercise 1.23 in Crandall & Pomerance  sean  Factoring  2  20061023 21:08 
The original paper on the Crandall/Fagin DWT  Barry Fagin  Math  2  20060104 19:46 
Crandall & Pomerance  Numbers  Math  16  20051016 00:53 
Question about a power series  Orgasmic Troll  Math  1  20040913 19:01 