mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-04-17, 05:41   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×683 Posts
Default 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
lavalamp is offline   Reply With Quote
Old 2010-04-17, 06:22   #2
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

1,777 Posts
Default

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
S485122 is offline   Reply With Quote
Old 2010-04-17, 06:33   #3
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×5×293 Posts
Default

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?
kar_bon is offline   Reply With Quote
Old 2010-04-17, 06:52   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2010-04-17, 07:00   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×683 Posts
Default

Quote:
Originally Posted by S485122 View Post
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 View Post
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.
lavalamp is offline   Reply With Quote
Old 2010-04-17, 07:13   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
10metreh is offline   Reply With Quote
Old 2010-04-17, 07:20   #7
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2·683 Posts
Default

Yeah, you're narrowing it down pretty quick now.
lavalamp is offline   Reply With Quote
Old 2010-04-17, 07:34   #8
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2010-04-17, 09:15   #9
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

101010101102 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2010-04-17, 11:05   #10
10metreh
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
10metreh is offline   Reply With Quote
Old 2010-04-17, 12:03   #11
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×683 Posts
Default

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.
lavalamp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring problem RedGolpe Factoring 9 2008-09-02 15:27
Problem with P-1 factoring... VolMike Software 5 2007-07-26 13:35
Prime95 v24.14 P-1 Factoring problem harlee Software 1 2006-12-19 22:19
Problem trial factoring + 64 bit EPF Hardware 2 2005-06-26 04:12
Factoring Problem asdf Puzzles 4 2003-08-30 17:56

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


Tue Jan 25 20:06:10 UTC 2022 up 186 days, 14:35, 1 user, load averages: 0.93, 1.19, 1.29

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔