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.
[Math] Set of numbers with no common factor that has max sum
algorithmsgcd-and-lcmnumber theoryoptimization
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:
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.
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
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:
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:
So:
New lists: