22
7
A fun pair of equivalences is 1 + 5 = 2 · 3 and 1 · 5 = 2 + 3. There are many like these, another one is 1 + 1 + 8 = 1 · 2 · 5 and 1 · 1 · 8 = 1 + 2 + 5. In general a product of n positive integers equals a sum of n positive integers, and vice versa.
In this challenge you must generate all such combinations of positive integers for an input n > 1, excluding permutations. You can output these in any reasonable format. For example, all the possible solutions for n = 3 are:
(2, 2, 2) (1, 1, 6)
(1, 2, 3) (1, 2, 3)
(1, 3, 3) (1, 1, 7)
(1, 2, 5) (1, 1, 8)
The program that can generate the most combinations for the highest n in one minute on my 2GB RAM, 64-bit Intel Ubuntu laptop wins. If your answer uses more than 2GB of RAM or is written in a language I can not test with freely available software, I will not score your answer. I will test the answers in two weeks time from now and choose the winner. Later non-competing answers can still be posted of course.
Since it's not known what the full sets of solutions for all n are, you are allowed to post answers that generate incomplete solutions. However if another answer generates a (more) complete solution, even if their maximum n is smaller, that answer wins.
To clarify, here's the scoring process to decide the winner:
I will test your program with n=2, n=3, etc... I store all your outputs and stop when your program takes more than a minute or more than 2GB RAM. Each time the program is run for a given input n, it will be terminated if it takes more than 1 minute.
I look at all the results for all programs for n = 2. If a program produced less valid solutions than another, that program is eliminated.
Repeat step 2 for n=3, n=4, etc... The last program standing wins.
1So no answers in windows-exclusive languages? – Conor O'Brien – 2017-07-30T20:15:59.967
3Personally, I dislike the scoring criteria. It's impossible to know whether our solutions will work and where to set the thresholds until we have results from the tests on your computer. I think a simple [tag:code-golf] would make a better question. – musicman523 – 2017-07-30T20:23:59.213
2I assume hardcoding is not allowed. But then that restriction is close to being unobservable – Luis Mendo – 2017-07-30T20:29:00.050
How do you define "more complete solution" with different n? It is even not known whether
number_of_solution(n)
is monotonically increasing. – user202729 – 2017-07-31T08:47:31.5471@user202729 I don't, I have to try each program for each n to see which program generates more solutions. – orlp – 2017-07-31T09:23:05.303
So the program with the largest number of solution will win regardless of n? I still don't understand how you test. BTW if a solution hardcode the value of n (the only answer now) is that allowed? – user202729 – 2017-07-31T09:28:26.920
@user202729 Hardcoding is not allowed in any fastest-code challenge. The idea is that the winning entry will generate complete solutions for all
n
, except the last, where it will run out of time. I don't know why people believe that generating incomplete solutions will give them any reasonable shot at winning. – orlp – 2017-07-31T09:36:47.050So if I can find 13 solution (which is incomplete) for n=6 I will win the existing answer, where if I find 11 solution (which is complete) for n=5 I will lose? So n is indeed irrelevant. – user202729 – 2017-07-31T09:41:46.573
@user202729 No, you misunderstand the rules and I'm tired of explaining this. I asked a moderator to delete this challenge. – orlp – 2017-07-31T11:45:54.680
Another question: do you mean one minute for a single value, or a minute for all possible values up to n? – G B – 2017-07-31T12:12:41.243
1@GB I hope that the clarifications made it clear your program gets up to one minute per n. – orlp – 2017-07-31T12:14:43.070
1I think the approach of not requiring proof of completeness is particularly elegant, as it gives people the opportunity to attack other answers by posting more complete ones, and for other answers to use imperfect heuristics until such attacks arrive. – trichoplax – 2017-07-31T12:38:54.350
Is Mathematica a freely available software? The trial version is available here.
– JungHwan Min – 2017-08-01T17:21:18.9172"Two weeks time from now" is 3 days ago. – G B – 2017-08-16T13:44:46.060
Two weeks are passed for me too... – RosLuP – 2017-08-29T07:20:23.500
I no longer like this challenge now that the announced scoring process doesn't happen, but I can't undo my upvote! – Christian Sievers – 2017-09-06T20:27:40.523
1@ChristianSievers and everyone else, I will score this challenge, but it will take me some time. I had underestimated how much work it would be, and I've been very much not in the mood for it in the past couple weeks and been postponing it. Currently I am sick as well. I apologize. I won't make another challenge where I have to install multiple languages to score answers again to prevent this in the future. – orlp – 2017-09-06T20:37:10.123
Good to hear you will still score it. I understand it is a lot of work. I really like fastest-code challenges, and this one was more interesting than it seemed at first. Hope you get well again soon! – Christian Sievers – 2017-09-07T01:46:47.237
But who had to say is not ok installing different programming languages... I like too fastcode tag, but for try all solution in different programing languages: one has to run below one minute and use some extern site... For here I think GB wins. I hope you all are in good health – RosLuP – 2017-09-07T06:42:56.453