17
4
The task is to find a non-trivial factor of a composite number.
Write code that finds a non-trivial factor of a composite number as quickly as possible subject to your code being no more than 140 bytes long. The output should just be the factor you have found.
Your code can take input and give output in any way that is convenient including for example as arguments to a function.
Test cases which list all the factors (you only need to output one)
187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697
I won't score your answer on the following difficult test case which may be of interest for testing:
513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471
Score
Your score is the combined time to factor all the test cases above with a penalty of 10 minutes for each failed factorization (all rounded to the nearest second). Your code should work for other integers too, that is shouldn't just hardcode these answers.
I will stop your code after 10 minutes.
If two people get the same score then the first answer wins.
Restrictions
Your code can't use any builtin or library function that performs integer factorization. You can assume the input takes less than 256 bits. All input numbers will be composite.
How will I time?
I will literally run time ./myprog
on my Ubuntu system to do the timing so please also supply a complete program for me to run that includes any function you have defined.
A note for compiled languages
Compilation time must take no more than 1 minute on my machine.
Is it actually possible?
If you ignore the space constraints, then each one can be factored in less than 2 seconds on my computer using pure Python code + pypy.
So what is a non-trivial factoring algorithm?
Pollard's rho algorithm is fast and suitable for golfing. Of course there are plenty of other ways to factor an integer as well.
Even faster is the Quadratic sieve. It looks like a serious challenge to squeeze that into 140 bytes.
Leading scores
- SEJPM, 10 minutes penalty for the last test case + 16 seconds in Haskell
So, we may be given a number like
2 ** 1024
? – Conor O'Brien – 2017-07-08T19:23:32.707@ConorO'Brien You won't be given anything with more digits than the test cases. – None – 2017-07-08T19:35:44.297
So, in terms of precision, nothing more than 256 bits. – Conor O'Brien – 2017-07-08T19:37:24.470
For an input like 4, should the output be
2
or2, 2
? – Mr. Xcoder – 2017-07-08T20:37:19.820Are you sure that the last test case is possible in 10 minutes? – LegionMammal978 – 2017-07-08T22:03:24.640
@LegionMammal978
msieve
(a dedicated C/C++ factoring tool) can solve the last test case in about 2 seconds.sage
needs about the same time with a simple call tofactor
. Whether it is feasible to put the algorithms used in these tools into 140 chars is a different question... – SEJPM – 2017-07-08T22:05:34.927The only answer so far breaks the specification by merely finding a factor of a composite number, and not a full prime factorization. However, perhaps that would a better challenge, so that one doesn’t need to squeeze both factoring and primality testing into the same tweet? (By themselves, I think the fastest factoring algorithms will tend to run slowly or loop infinitely trying to factor the remaining primes after all the proper factors have been found.) – Anders Kaseorg – 2017-07-08T22:52:38.523
1@AndersKaseorg I updated the question following your suggestion. Thanks. – None – 2017-07-09T06:05:08.140
Why the downvote? Please add an explanation. I may even be able to fix what you don't like. – None – 2017-07-09T11:02:35.463
@Lembik I suppose in the Haskell solution the 1751952685614616185916001760791655006749 would be the number not factored in 10 minutes; so I suppose you say that for factoring 82312263010898855308580978867 Haskell code take 16 seconds? How is possible than in Tio that code in 1 minute (I suppose) not factored it? – RosLuP – 2017-09-28T19:12:46.343