Programming and factoring problem

[CRGreathouse]

Answer: 10^399+31 = 615683907928640460029 * p379

[10metreh]

Originally Posted by lavalamp

Yes, I was going to install GMP-ECM, but alas sourceforge is down so I cannot fetch MinGW and MSYS.

You can get precompiled Windows binaries from here.

[lavalamp]

Yep CRGreathouse, that's what I get too.

Originally Posted by 10metreh

You can get precompiled Windows binaries from here.

Ah, very handy. That's probably saved me a fair amount of shouting at my computer screen.

Easy extension, swop out, "400 digit number" with 100, 200, 300, 500 digit number. I think we may have gotten lucky that the answer for the 400 digit puzzle had a nice attainable factor, but surely that won't be the case for them all.

[axn]

100 digits = 10^99+9
300 digits = 10^299+59

[Jens K Andersen]

In 2002 CYF NO. 11 at http://www.shyamsundergupta.com/canyoufind.htm asked for the smallest titanic semiprime. It is either 10^999+13 (no known factor) or 10^999+139 = 31*p998. I made a brief and Paul Zimmermann a longer search for a factor of 10^999+13. Can somebody settle it after 8 years of software and hardware improvements?

[CRGreathouse]

Do you know how much work has been done on 10^999+13?

[ET_]

Originally Posted by CRGreathouse

Do you know how much work has been done on 10^999+13?

IIRC, at least 1800 ecm curves with B1=1000000, B2=100000000.

Luigi

[Jens K Andersen]

I only know what CYF NO. 11 quotes Paul Zimmermann for in 2002: "I performed 1800 ecm curves with 1st stage bound B1=1000000 with 10^999+13 without any success. So it seems that its smallest prime factor is larger than 35 digits. I also tried a large P-1 run and it failed too."

[lavalamp]

Here is the full information from the website on this particular problem (CYF NO. 11).

Originally Posted by http://www.shyamsundergupta.com/canyoufind.htm

The smallest titanic (containing 1000 digits or more) Semiprime (Product of two primes)

(Comments by Patrick De Geest vide his email dt. 17-09-2002 & 18-09-2002).

Patrick De Geest says in his email that "I ran Ubasic and soon my program gave the following smallest Titanic EVEN Semiprime. 10^999+5026 = (2) * (5*10^998 +2513). In his subsequent email , he says that the smallest titanic semiprime MIGHT be 10^999 +139 , provided I can 'exclude' the following two numbers: 10^999 + 13 and 10^999 + 69, Both numbers have smaller factor larger than 10^8. I guess that this is the hard part of the puzzle".

(Comments by Jens Kruse Andersen vide his email dt. 18-09-2002 ).

Jens Kruse Andersen says in his emails that " The smallest titanic semiprime is either 10^999+13 or 10^999+139. 10^999+139 is a proven semiprime with prime factor 31 and cofactor (10^999+139)/31 proved prime with Primo and validated by Cert_Val. 10^999+13 is composite but I have found no factors and don't know how many there are. After running GMP-ECM for several hours, the smallest factor is probably at least 25 digits and hard to find. I have not heard of any semiprime test without a known factor. 10^999+7 is prime. According to Primeform/GW all remaining numbers below 10^999+139 have a relatively small prime factor with a composite cofactor. The only numbers without a factor below 500000 are 10^999+19 (factor: 2698217) and 10^999+69 (factor: 3067890809). Of course the question remains: Can anyone determine whether 10^999+13 is a semiprime?

(Comments by Paul Zimmermann vide his email dt. 12-11-2002 ).

Paul Zimmermann says in his emails that " I performed 1800 ecm curves with 1st stage bound B1=1000000 with 10^999+13 without any success. So it seems that its smallest prime factor is larger than 35 digits. I also tried a large P-1 run and it failed too."

I'd be willing to throw some curves at it in a few hours when I finish this current candidate for OBD.

[Jens K Andersen]

http://users.skynet.be/worldofnumbers/em144.htm asks for the first gigantic semiprime. In 2005 I found the candidate 10^9999+1253 = 3*prp9999, and 30 smaller numbers with no known factor: 10^9999 + k, for k = 19, 37, 87, 97, 121, 193, 207, 213, 273, 283, 327, 427, 439, 543, 679, 693, 721, 789, 811, 843, 867, 891, 949, 999, 1039, 1053, 1081, 1089, 1231, 1237.

The factorization effort was low and some of them probably have relatively easy factors.

[axn]

If anybody is planning to do ECM on this number, be sure to use Prime95 (v25.11) for stage 1 and gmp-ecm for stage2