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

The following is quite practical.

Let N = {1, 2, 3, ..., n}. Let p1 < p2 < p3 < ... < pk be the primes in N. Let Ti be the natural numbers in N divisible by pi but not by any prime less than pi. We can pick at most one number from each subset Ti.

Now recurse. S = {1}. Check if pi is a divisor of any of the numbers already in S. If it is, skip Ti. Otherwise, pick a number xi from Ti coprime to the elements already in S, and add it to S. Go to next i.

When we reach k + 1, calculate the sum of the elements in S. If new maximum, save S away.

Continue.

Take n = 30. The primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

T1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30}
T2 = {3, 9, 15, 21, 27}
T3 = {5, 25}
T4 = {7}
T5 = {11}
T6 = {13}
T7 = {17}
T8 = {19}
T9 = {23}
T10 = {29}

So fewer than 15 * 5 * 2 = 150 possibilities.

Here is my original wrong result for n = 100.

1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 88 89 91 95 97 99
Sum = 1374

It should be

1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 81 83 88 89 91 95 97
Sum = 1356

Less than 2 seconds for n = 150. About 9 seconds for n = 200.

Answer 2

I implemented a recursive solution in Prolog, based on taking the list of integers in descending order. On my fairly ancient Toshiba laptop, SWI-Prolog produces answers without hesitation for N < 90. Here are some timings for N = 100 to 150 by tens:

  N         Sum       Time(s)
-----    ---------    -------
 100        1356         1.9
 110        1778         2.4
 120        1962         4.2
 130        2273        11.8
 140        2692        16.3
 150        2841        30.5

The timings reflect an implementation that starts from scratch for each value of N. A lot of the computation for N+1 can be skipped if the result for N is previously known, so if a range of values N are to be computed, it would make sense to take advantage of that.

Prolog source code follows.

/*
   Check if two positive integers are coprime
   recursively via Euclid's division algorithm
*/
coprime(0,Z) :- !, Z = 1.
coprime(A,B) :-
    C is B mod A,
    coprime(C,A).

/*
   Find the sublist of first argument that are
   integers coprime to the second argument
*/
listCoprime([ ],_,[ ]).
listCoprime([H|T],X,L) :-
    (   coprime(H,X)
     -> L = [H|M]
     ;  L = M
    ),
    listCoprime(T,X,M).

/*
   Find the sublist of first argument of coprime
   integers having the maximum possible sum
*/
sublistCoprimeMaxSum([ ],S,[ ],S).
sublistCoprimeMaxSum([H|T],A,L,S) :-
    listCoprime(T,H,R),
    B is A+H,
    sublistCoprimeMaxSum(R,B,U,Z),
    (   T = R
     -> ( L = [H|U], S = Z )
     ;  ( sublistCoprimeMaxSum(T,A,V,W),
          (   W < Z
           -> ( L = [H|U], S = Z )
           ;  ( L = V, S = W )
          )
        )
    ).

/*    Test utility to generate list N,..,1   */
list1toN(1,[1]).
list1toN(N,[N|L]) :-
    N > 1,
    M is N-1,
    list1toN(M,L).

/*    Test calling sublistCoprimeMaxSum/4   */
testCoprimeMaxSum(N,CoList,Sum) :-
    list1toN(N,L),
    sublistCoprimeMaxSum(L,0,CoList,Sum).

Answer 3

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!)

Answer 4

I think that this is similar to the subset problem, which is NP-Complete.

First, break each number into its prime factors (or use a list of primes to generate the full list from 1 to n, same thing).

Solve the subset problem with recursive descend by finding a subset that contains no common primes.

Run through all solutions and find the largest one.

Answer 5

You can do a little better by taking powers of primes, up the to bound you have. For example, suppose that n=30. Then you want to start with

1, 16, 27, 25, 7, 11, 13, 17, 19, 23, 29

Now look at where there are places to improve. Certainly you cannot increase any of the primes that are already at least n/2: 17, 19, 23, 29 (why?). Also, 3^3 and 5^2 are pretty close to 30, so they're also probably best left alone (why?).

But what about 2^4, 7, 11 and 13? We can take the 2's and combine them with 7, 11, or 13. This would give:

2 * 13 = 26 replaces 16 + 13 = 29 BAD
2 * 11 = 22 replaces 16 + 11 = 27 BAD
2^2 * 7 = 28 replaces 16 + 7 = 23 GOOD

So it looks like we should get the following list (now sorted):

1, 11, 13, 17, 19, 23, 25, 27, 28, 29

Try to prove that this cannot be improved, and that should give you some insight into the general case.

Good luck!