2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting question! Makes me wish I had gone to that interview :) For another interesting variation, try creating an algorithm that will work on ANY set of positive integers greater than 2, regardless of whether they start from 2 and regardless of whether they are consecutive. (P.S.: I only edited your tags, left the post exactly as-is.) $\endgroup$ – Wildcard Oct 6 '15 at 7:33
1
$\begingroup$

I think this might be correct-

{30, 29, 23, 19, 17, 13, 11, 7}.

I started from 30 and excluded all even numbers.

I included primes, if any factor of the prime did not appear beforehand. For example, 29, 23 etc are included but primes like 5(because 30 is included), 3(because 30 is included) are excluded.

-------------EDIT------------

This is a better result {11,13,17,19,23,25,27,28,29}.

Except for 25,27,28 all are primes. $25=5^2$, $27=3^3$, $28=2^2*7$. So no common factors.

Sum is 192.

$\endgroup$
  • $\begingroup$ 30 and 27 share a common factor. $\endgroup$ – Kyle Miller Oct 6 '15 at 6:28
  • $\begingroup$ Sorry for that. $\endgroup$ – Epsilon Oct 6 '15 at 6:52
  • $\begingroup$ This is like LCM(2,3,5), along with other primes in the specified range. $\endgroup$ – Epsilon Oct 6 '15 at 7:05
  • $\begingroup$ I have deleted my answer. You are right. But the whole idea of optimizing was OK. I am upvoting your answer. $\endgroup$ – Shailesh Oct 6 '15 at 7:19
  • $\begingroup$ Aha, you got it correctly before I posted! Nice! :) I had the answer quickly but took a while to write up my algorithm. $\endgroup$ – Wildcard Oct 6 '15 at 7:27
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Some further thoughts: I think the removal of "multiples of base lower than highest power of base" applies to ALL numbers, not only primes. So in the 2-1000 set, you would keep 1000 and remove ALL MULTIPLES of 10. Of course, 625+512 > 1000 anyway, so you won't be keeping 1000, but with 1000 in the set at all there is no circumstance where any lower multiple of 10 would be present in the final answer. $\endgroup$ – Wildcard Oct 6 '15 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.