[Math] Set of numbers with no common factor that has max sum

algorithmsgcd-and-lcmnumber theoryoptimization

Interview question I got today. Find the set of numbers between 2 and 30, with no common factor (e.g. gcd(28,24) = 2, so they cannot be in the same set) that will you give you a max sum? Using the same rules, what is the highest possible number you can have in a set of 1000?
I am thinking of using some kind of greedy algorithm to solve this but not sure if there is any other good solution.

Best Answer

The answer is {11,13,17,19,23,25,27,28,29} with a sum of 192

The following greedy algorithm is NOT correct, though it's highly tempting to think it is:

  1. Arrange the numbers in descending order. This is "the list".
  2. Start with an empty set that will be the eventual answer. This is "the set".
  3. For each item on the list:
  4. If it has a common factor with any item in the set, discard it.
  5. Otherwise, add it to the set.
  6. Move to the next item in the list and go to step 4.
  7. When the list is empty, the set contains the solution to the problem.

A simple counter-example as a proof of incorrectness:

The numbers 2-10, run through the above algorithm, produce the set {10,9,7} with a sum of 26. The correct answer is {5,7,8,9} with a sum of 29.

A partial algorithm which is sufficient for the 2-30 case is as follows. This involves a list of possibilities created through elimination, and a list of probable elements to include created by construction.

  1. Start with "possible list" containing all numbers you are concerned with.

    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30

  2. For each prime in the list, locate its highest power that is in the list. In the 2-30 case, this gives 16,27,25,7,11,13,17,19,23,29. Remove these from the "possible list" and place them in the "probable list".

New lists:

2,3,4,5,6,8,9,10,12,14,15,18,20,21,22,24,26,28,30
7,11,13,16,17,19,23,25,27,29

3. For any number in the probable list that is non-prime (i.e. it is a square or greater power of a prime), eliminate from the possible list all multiples of the base prime smaller than that power. (Based on 16,27,25, remove 2,4,6,8,10,12,14,3,9,15,18,21,24,5,20 from the list of possibilities.)

New lists:

22,26,28,30
7,11,13,16,17,19,23,25,27,29
  1. For each number remaining in the possible list, compare it to the sum of the numbers in the probable list which share factors with it. If it is less than that sum, remove it from the possible list.

So:

22 < 11+16 so remove 22
26 < 13+16 so remove 26
28 > 7+16 so leave it alone
30 < 16+27+25 so remove 30

New lists:

28
7,11,13,16,17,19,23,25,27,29
  1. In this case it is simple as there is only one left in the possibile list and it is greater than the prime powers it will replace, so it is put in the probable list, displacing 7 and 16, and that is the end of it. For much larger numbers, I haven't developed the algorithm.
Related Question