20100417, 05:41  #1 
Oct 2007
Manchester, UK
2×683 Posts 
Programming and factoring problem
Here's a puzzle I set for myself earlier (and completed, so I guess it can't be that hard ), I thought maybe some people here would find it moderately interesting also.
What is the smallest composite 400 digit number to have only two prime factors? Also, what is the smallest of those prime factors? Edit: I suppose 10^399 would technically be correct, since it is 2^399 * 5^399 and there are only two primes there. Sadly I don't think I can properly express what I mean here, so I'll simply say, no indices in the answer please. Last fiddled with by lavalamp on 20100417 at 05:47 
20100417, 06:22  #2 
"Jacob"
Sep 2006
Brussels, Belgium
1,777 Posts 
Would this rewording of the question correspond better to your puzzle ?
What is the smallest positive integer of 400 digit (expressed in base 10) that is the product of two prime integers. Jacob 
20100417, 06:33  #3 
Mar 2006
Germany
2×5×293 Posts 
N = 2^399 * 5^399 contains more than 2 primefactors!
A number N = p * q (p, q prime) is called a SemiPrime. Is that perhaps, what you mean? 
20100417, 06:52  #4 
Nov 2008
912_{16} Posts 
10^399+231 is the smallest one that we know to be a semiprime: 3191 * prp396.
I've checked all the 400digit numbers below it, and the following have passed one FactorDB Quick ECM without any factors found: Code:
10^399+9
10^399+31
10^399+37
10^399+49
10^399+109
Last fiddled with by 10metreh on 20100417 at 07:13 
20100417, 07:00  #5  
Oct 2007
Manchester, UK
2×683 Posts 
Quote:
This is what I thought too, but just wanted to clarify in case I was wrong. I did think there was such a term as semiprime, I just didn't know what it was, so yes, that. 10metreh, I'm afraid that's not the answer, but it is one of the low ones I found on my way to it. In case anyone else wants to try could you please use the spoiler tags next time. 

20100417, 07:13  #6  
Nov 2008
912_{16} Posts 
Quote:
Is the correct answer one of the five which I posted as having no known factors? Edit: It isn't 10^399+9: it has the factor 370532973872350691 and a composite cofactor. lavalamp, did you prove that all the numbers below your answer weren't semiprimes? Last fiddled with by 10metreh on 20100417 at 07:26 

20100417, 07:20  #7 
Oct 2007
Manchester, UK
2·683 Posts 
Yeah, you're narrowing it down pretty quick now.

20100417, 07:34  #8 
Nov 2008
2×3^{3}×43 Posts 
10^399+49 is gone: factor 181719501267767 and composite cofactor.
Edit: t20 done on all the rest. Moving on... Edit2: I'm not going any further right now. Last fiddled with by 10metreh on 20100417 at 07:46 
20100417, 09:15  #9 
Oct 2007
Manchester, UK
10101010110_{2} Posts 
Ah, so close and you walk away!
If it helps at all, I got a fair amount of mileage out of this handy dandy only Java ECM program: http://www.alpertron.com.ar/ECM.HTM It's pretty much my first stop whenever I want something factored quickly. Though I'm sure there are perhaps faster programs written in C that can be run from the command line. 
20100417, 11:05  #10  
Nov 2008
912_{16} Posts 
Quote:
Last fiddled with by 10metreh on 20100417 at 11:05 

20100417, 12:03  #11 
Oct 2007
Manchester, UK
2×683 Posts 
Yes, I was going to install GMPECM, but alas sourceforge is down so I cannot fetch MinGW and MSYS.
I found it slightly confusing that you were running a few curves on each rather than concentrating on the smallest candidates first. Afterall, you're looking for the smallest one. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring problem  RedGolpe  Factoring  9  20080902 15:27 
Problem with P1 factoring...  VolMike  Software  5  20070726 13:35 
Prime95 v24.14 P1 Factoring problem  harlee  Software  1  20061219 22:19 
Problem trial factoring + 64 bit  EPF  Hardware  2  20050626 04:12 
Factoring Problem  asdf  Puzzles  4  20030830 17:56 