-7
\$\begingroup\$

Challenge

Write a program to factor this set of 10 numbers:

15683499351193564659087946928346254200387478295674004601169717908835380854917
24336606644769176324903078146386725856136578588745270315310278603961263491677
39755798612593330363515033768510977798534810965257249856505320177501370210341
45956007409701555500308213076326847244392474672803754232123628738514180025797
56750561765380426511927268981399041209973784855914649851851872005717216649851
64305356095578257847945249846113079683233332281480076038577811506478735772917
72232745851737657087578202276146803955517234009862217795158516719268257918161
80396068174823246821470041884501608488208032185938027007215075377038829809859
93898867938957957723894669598282066663807700699724611406694487559911505370789
99944277286356423266080003813695961952369626021807452112627990138859887645249

Each of these:

  • Is a 77-digit number less than 2^256.
  • Is a semiprime (e.g., the product of exactly 2 primes).
  • Has something in common with at least one other number in the set.

Thus, this challenge is not about general factoring of 256-bit semiprimes, but about factoring these semiprimes. It is a puzzle. There is a trick. The trick is fun.

It is possible to factor each of these numbers with surprising efficiency. Therefore, the algorithm you choose will make a much bigger difference than the hardware you use.

Rules

  1. This is , so the shortest answer wins.
  2. You may use any method of factoring. (But don't precompute the answers and just print them. You program should do actual work.)
  3. You may use any programming language (or combination of languages), and any libraries they provide or you have installed. However, you probably won't need anything fancy.
\$\endgroup\$

closed as off-topic by rink.attendant.6, Alex A., Luis Mendo, xnor, PurkkaKoodari Aug 24 '15 at 5:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – rink.attendant.6, Alex A., Luis Mendo, xnor, PurkkaKoodari
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ @BrainSteel — Just these. However, it should actually do some work. Don't simply write a program that executes in 0.00 seconds that prints out the factorizations from hard-coded values after figuring them out using a slower method. :) \$\endgroup\$ – Todd Lehman Aug 23 '15 at 2:21
  • 4
    \$\begingroup\$ But using the same algorithm on two different computers will. If your not going to test the solutions yourself, the scores will be unverifiable and the contest will boil down to who has the fastest computer. Most languages should be easy enough to install. If you choose this route, I'd recommend forbidding languages without a free interpreter. \$\endgroup\$ – Dennis Aug 23 '15 at 3:14
  • 3
    \$\begingroup\$ @GlenO Is it? I've tried William's p+1, Pollard's p-1, Fermat's near semi-primes, but none of them matched. To save others the effort, the factorization of the first number is 123830525223423718982054269884856893727 and 126652934104061135988638942588043498971. \$\endgroup\$ – orlp Aug 23 '15 at 5:03
  • 3
    \$\begingroup\$ I have a solution sitting ready to post, and it runs in milliseconds, but don't want to post it too quickly, because it gives away the puzzle. \$\endgroup\$ – Glen O Aug 23 '15 at 5:19
  • 4
    \$\begingroup\$ @GlenO: This isn't puzzling.SE; IMO go ahead. (This challenge is flawed and doesn't really fit here, and I've downvoted it. It's a fine puzzle, but a horrible fastest-code challenge.) \$\endgroup\$ – Lynn Aug 23 '15 at 5:20
4
\$\begingroup\$

Pyth, 12 bytes

V.Q--iRN.Q1N

Try it here: Demonstration

Explanation:

               implicit: .Q is the list of the input numbers
V.Q            for N in .Q:
     iRN.Q        compute the gcd of N with each number in .Q
    -     1       remove 1s
   -       N      remove the number N and print
\$\endgroup\$
  • \$\begingroup\$ WOW! Unbelievable! Awesome. \$\endgroup\$ – Todd Lehman Aug 23 '15 at 6:12
  • \$\begingroup\$ I don't know how I could forget about .Q... \$\endgroup\$ – orlp Aug 23 '15 at 6:13
3
\$\begingroup\$

Julia

f=l->(A=map(big,[gcd(l[i],l[j]) for i=1:length(l),j=1:length(l)]);A-=eye(A).*(l-1);for i=1:length(l) println(l[i]," = ",join(unique(A[i,:])," × "))end);

Running it:

julia> tic();f(l);toc()
15683499351193564659087946928346254200387478295674004601169717908835380854917 = 1 × 123830525223423718982054269884856893727 × 126652934104061135988638942588043498971
24336606644769176324903078146386725856136578588745270315310278603961263491677 = 123830525223423718982054269884856893727 × 1 × 196531562802139162910711939551924590851
39755798612593330363515033768510977798534810965257249856505320177501370210341 = 126652934104061135988638942588043498971 × 1 × 313895598975456800331958744266933545471
45956007409701555500308213076326847244392474672803754232123628738514180025797 = 1 × 196531562802139162910711939551924590851 × 233835251470362519313085185758275325847
56750561765380426511927268981399041209973784855914649851851872005717216649851 = 1 × 218051709768607497734800854124975705007 × 260261943488556401874345256435550440693
64305356095578257847945249846113079683233332281480076038577811506478735772917 = 1 × 218051709768607497734800854124975705007 × 294908745103709254641398276907437631131
72232745851737657087578202276146803955517234009862217795158516719268257918161 = 1 × 233835251470362519313085185758275325847 × 308904433345854212511531098349325333463
80396068174823246821470041884501608488208032185938027007215075377038829809859 = 1 × 260261943488556401874345256435550440693 × 308904433345854212511531098349325333463
93898867938957957723894669598282066663807700699724611406694487559911505370789 = 1 × 294908745103709254641398276907437631131 × 318399740590727338211743341325021840319
99944277286356423266080003813695961952369626021807452112627990138859887645249 = 1 × 313895598975456800331958744266933545471 × 318399740590727338211743341325021840319
elapsed time: 0.002534739 seconds

Note: Because of how Julia operates, you might want to run it twice - the first time you run it, the tic/toc will include the time required to "compile" it. The second time, it will have already compiled it.

\$\endgroup\$
  • \$\begingroup\$ Nice work! Much shorter than my Perl solution. \$\endgroup\$ – Todd Lehman Aug 23 '15 at 5:30
3
\$\begingroup\$

CJam, 32 bytes

q~]__ff{{_@\%}h}:|1-_m*_::*\er:p

Try it online: permalink for Chrome | permalink for Firefox

\$\endgroup\$
2
\$\begingroup\$

CJam, 38 bytes

q~]_2m*{~{_@\%}h;}%_2$-&2m*f{_::*@#=p}

Try it here.

This answer is shorter than any of the factors in the output.

\$\endgroup\$
  • \$\begingroup\$ Hahaha, holy smokes, that's impressive. I may have to learn CJam now. That's just...wow. Best part is, the trick isn't visible from eyeballing the code! :) \$\endgroup\$ – Todd Lehman Aug 23 '15 at 5:45
2
\$\begingroup\$

J, 2 bytes

This is now, so I assume efficiency doesn't actually matter, which means:

q:

(J's "factor prime" function) will return the right answer (in the form of a neatly formatted 2x10 array!) if you pass it an array of bignums give it a couple of hours/days to factor the semiprimes.

\$\endgroup\$
  • \$\begingroup\$ LOL. Welp, I hadn't anticipated that loophole! :-o :-) \$\endgroup\$ – Todd Lehman Aug 23 '15 at 6:15
  • \$\begingroup\$ @ToddLehman I wouldn't call this a loophole per se \$\endgroup\$ – Beta Decay Aug 23 '15 at 9:01
1
\$\begingroup\$

Pyth, 15 13 12 bytes

jbmS{iLd.Q.Q

Expects the list of primes seperated by newlines on stdin. Outputs in the following format:

[1, 123830525223423718982054269884856893727, 126652934104061135988638942588043498971, 15683499351193564659087946928346254200387478295674004601169717908835380854917]
[1, 123830525223423718982054269884856893727, 196531562802139162910711939551924590851, 24336606644769176324903078146386725856136578588745270315310278603961263491677]
[1, 126652934104061135988638942588043498971, 313895598975456800331958744266933545471, 39755798612593330363515033768510977798534810965257249856505320177501370210341]
[1, 196531562802139162910711939551924590851, 233835251470362519313085185758275325847, 45956007409701555500308213076326847244392474672803754232123628738514180025797]
[1, 218051709768607497734800854124975705007, 260261943488556401874345256435550440693, 56750561765380426511927268981399041209973784855914649851851872005717216649851]
[1, 218051709768607497734800854124975705007, 294908745103709254641398276907437631131, 64305356095578257847945249846113079683233332281480076038577811506478735772917]
[1, 233835251470362519313085185758275325847, 308904433345854212511531098349325333463, 72232745851737657087578202276146803955517234009862217795158516719268257918161]
[1, 260261943488556401874345256435550440693, 308904433345854212511531098349325333463, 80396068174823246821470041884501608488208032185938027007215075377038829809859]
[1, 294908745103709254641398276907437631131, 318399740590727338211743341325021840319, 93898867938957957723894669598282066663807700699724611406694487559911505370789]
[1, 313895598975456800331958744266933545471, 318399740590727338211743341325021840319, 99944277286356423266080003813695961952369626021807452112627990138859887645249]
\$\endgroup\$
1
\$\begingroup\$

Pyth, 4 bytes

Since we don't have to abuse the common divisors we can simply use the factorization function and map it to the input:

PM.Q

Yay loopholes!

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.