17
3
Executive summary
Given input k
, find a partition of integers 1
to n
into k
sum-free subsets for the largest n
you can within 10 minutes.
Background: Schur numbers
A set A
is sum-free if its self-sum A + A = { x + y | x, y in A}
has no elements in common with it.
For every positive integer k
there is a largest integer S(k)
such that the set {1, 2, ..., S(k)}
can be partitioned into k
sum-free subsets. This number is called the kth Schur number (OEIS A045652).
For example, S(2) = 4
. We can partition {1, 2, 3, 4}
as {1, 4}, {2, 3}
, and that is the unique partition into two sum-free subsets, but we can't now add a 5
to either part.
Challenge
Write a deterministic program which does the following:
- Take a positive integer
k
as input - Write the current Unix timestamp to stdout
- Outputs a sequence of partitions of
1
ton
intok
sum-free subsets for increasingn
, following each sequence with the current Unix timestamp.
The winner will be the program which prints a partition for the largest n
within 10 minutes on my computer when given input 5
. Ties will be broken by the quickest time to find a partition for the largest n
, averaged over three runs: that's why the output should include timestamps.
Important details:
- I have Ubuntu Precise, so if your language is not supported I will be unable to score it.
- I have an Intel Core2 Quad CPU, so if you want to use multithreading there's no point using more than 4 threads.
- If you want me to use any particular compiler flags or implementation, document that clearly in your answer.
- You shall not special-case your code to handle the input
5
. - You are not required to output every improvement you find. E.g. for input
2
you could output only the partition forn = 4
. However, if you don't output anything in the first 10 minutes then I will score that asn = 0
.
Note: sorting by greatest number of allowed numbers within the range of disallowed numbers gives
n=59
, and sorting by greatest number of allowed numbers less thannextN
givesn=64
. Sorting by the length of the disallowed numbers list (which may have repeats) leads very quickly to an elegantn=30
pattern. – El'endia Starman – 2015-11-09T23:39:56.517The output time format isn't correct (should be seconds since the epoch, but I'm seeing
Tue Nov 10 00:44:25 2015
), but I sawn=92
in less than 2 seconds. – Peter Taylor – 2015-11-09T23:46:22.977Ah, I figured that the time format wasn't as important as showing exactly how long it took. I'll figure it out and change it though. EDIT: D'oh. I picked
ctime
overtime
because the output was prettier whentime
was exactly what I should've picked. – El'endia Starman – 2015-11-10T01:44:15.047You know, you could also just sort by greatest number in the bin, because the greatest disallowed number will always be twice that. – Martin Ender – 2015-11-10T08:05:04.230
@MartinBüttner: ......I...uh...I have no idea how or why, but that gets
n=121
. o.O – El'endia Starman – 2015-11-10T08:21:11.013