finding maximal subsets

Question

For given n, find the subset S of {1,2,...,n} such that

1. all elements of S are coprime
2. the sum of the elements of S is as large as possible

Doing a brute force search takes too long and I can't find a pattern. I know that I can just take all the primes from 1 to n, but that's probably not the right answer. Thanks.

Answer 1

I would tackle this as a dynamic programming problem. Let me walk through it for 20. First take the primes in reverse order.

19, 17, 13, 11, 7, 5, 3, 2

Now we're going to walk up the best solutions which have used subsets of those primes of increasing size. We're going to do a variation of breadth first search, but with the trick that we always use the largest currently unused prime (plus possibly more). I will represent all of the data structures in the form size: {set} = (total, next_number). (I'm doing this by hand, so all mistakes are mine.) Here is how we build up the data structure. (In each step I consider all ways of growing all sets of one smaller size from the previous step, and take the best totals.)

Try to reproduce this listing and, modulo any mistakes I made, you should have an algorithm.

Step 0
0: {} => (1, 1)

Step 1
1: {19} => (20, 19)

Step 2
2: {19, 17} => (37, 17)

Step 3
3: {19, 17, 13} => (50, 13)

Step 4
4: {19, 17, 13, 11} => (61, 11)

Step 5
5: {19, 17, 13, 11, 7} => (68, 7)

6: {19, 17, 13, 11, 7, 2} => (75, 14)

Step 6
6: {19, 17, 13, 11, 7, 5} => (73, 5)
   {19, 17, 13, 11, 7, 2} => (75, 14)

7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

Step 7
7: {19, 17, 13, 11, 7, 5, 2} => (88, 20)
   {19, 17, 13, 11, 7, 5, 3} => (83, 15)

8: {19, 17, 13, 11, 7, 5, 3, 2} => (91, 18)

Step 8
8: {19, 17, 13, 11, 7, 5, 3, 2} => (99, 16)

And now we just trace the data structures backwards to read off 16, 15, 7, 11, 13, 17, 19, 1 which we can sort to get 1, 7, 11, 13, 15, 16, 17, 19.

(Note there are a lot of details to get right to turn this into a solution. Good luck!)