mersenneforum.org Programming and factoring problem
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-17, 05:41 #1 lavalamp     Oct 2007 Manchester, UK 2×5×137 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 2010-04-17 at 05:47
 2010-04-17, 06:22 #2 S485122     "Jacob" Sep 2006 Brussels, Belgium 71816 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
 2010-04-17, 06:33 #3 kar_bon     Mar 2006 Germany 23×32×41 Posts N = 2^399 * 5^399 contains more than 2 prime-factors! A number N = p * q (p, q prime) is called a Semi-Prime. Is that perhaps, what you mean?
 2010-04-17, 06:52 #4 10metreh     Nov 2008 91216 Posts 10^399+231 is the smallest one that we know to be a semiprime: 3191 * prp396. I've checked all the 400-digit 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 All the others have either (a) factor(s) and a composite cofactor, or more than one small factor and a prime cofactor, meaning they cannot be semiprimes. Last fiddled with by 10metreh on 2010-04-17 at 07:13
2010-04-17, 07:00   #5
lavalamp

Oct 2007
Manchester, UK

2·5·137 Posts

Quote:
 Originally Posted by S485122 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
Sounds good.

Quote:
 Originally Posted by kar_bon N = 2^399 * 5^399 contains more than 2 prime-factors!
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 semi-prime, 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.

2010-04-17, 07:13   #6
10metreh

Nov 2008

232210 Posts

Quote:
 Originally Posted by lavalamp 10metreh, I'm afraid that's not the answer, but it is one of the low ones I found on my way to it.
Spoilers done.

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 2010-04-17 at 07:26

 2010-04-17, 07:20 #7 lavalamp     Oct 2007 Manchester, UK 2·5·137 Posts Yeah, you're narrowing it down pretty quick now.
 2010-04-17, 07:34 #8 10metreh     Nov 2008 44228 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 2010-04-17 at 07:46
 2010-04-17, 09:15 #9 lavalamp     Oct 2007 Manchester, UK 2×5×137 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.
2010-04-17, 11:05   #10
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by lavalamp 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.
I was using GMP-ECM on an ancient P4. I would have continued had I not been concentrating on other things. GMP-ECM is faster than Alpertron's applet on this machine.

Last fiddled with by 10metreh on 2010-04-17 at 11:05

 2010-04-17, 12:03 #11 lavalamp     Oct 2007 Manchester, UK 2×5×137 Posts Yes, I was going to install GMP-ECM, 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post RedGolpe Factoring 9 2008-09-02 15:27 VolMike Software 5 2007-07-26 13:35 harlee Software 1 2006-12-19 22:19 EPF Hardware 2 2005-06-26 04:12 asdf Puzzles 4 2003-08-30 17:56

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

Sat May 28 19:06:59 UTC 2022 up 44 days, 17:08, 0 users, load averages: 2.63, 1.96, 1.55