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

[url]http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000945[/url]

[url]http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000946[/url]

Looks like no recent progress on either series.

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.

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 [url]http://www.alpertron.com.ar/ECM.HTM[/url]

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

[QUOTE=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.[/QUOTE]
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

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.

Thanks, will do.

Using the applet I have run curves number 800-850.

I've done up through 35 digits (1e6)... We can probably coordinate to do 40 digits very quickly...

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

[QUOTE=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)[/QUOTE]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[/code]