Pick however many integers in the range $[1,30]$ (inclusive). The only constraint is that all of these numbers must be relatively prime to each other.

What is the largest possible arithmetic sum from this construction?

I think that I should start from the list of primes and then try deducing a possible answer from eliminating different combinations starting from the largest number that is not prime (i.e. 28). However, I don't know how to show that such combination is the largest possible.

I would also be interested in different ways to approach this problem.

  • I think that the highest you can get is $1+2^4+3^3+5^2+7+11+13+17+19+23+29$. – Leafar Jul 20 '15 at 4:56
  • 1
    @Leafar I can beat that: $1 + 11 + 13 + 17 + 19 + 23 + 25 + 27 + 28 + 29 = 193$ – Jared Jul 20 '15 at 5:19
  • I just want to point out that it's not always the case that you should use the largest non-prime (28 in your case). Consider the largest sum from 1-11: $1 + 5 + 7 + 8 + 9 + 11 = 41$. The sum doesn't change once you go to 1-12 because $12 < 9 + 8$ thus you should not include $12$. You should include $28$ in your case because $28 > 7 + 16$. – Jared Jul 20 '15 at 5:36
  • The question came up elsewhere some time ago, see stackoverflow.com/questions/5393716/finding-maximal-subsets – Gerry Myerson Jul 20 '15 at 7:22
up vote 1 down vote accepted

You can use integer linear programming: maximize $\sum_{i=1}^{30} i x_i$ subject to $x_i + x_j \le 1$ for each non-relatively-prime pair $(i,j)$, and all $x_i \in \{0,1\}$.

EDIT: Cplex takes very little time to come up with the same solution Jared found. Even for a problem with numbers going from $1$ to $150$ instead of $1$ to $30$, it took only about 4.5 seconds.

  • Whoa! That's a really cool way of solving this problem! Thank you so much! p.s. I grew up 10 minutes drive from UBC, although I go to school in the States now :-) – Andy Yao Jul 20 '15 at 14:03

If you're going to try and do this with trial and error then I think Leafar is where you should start--not from just a sum of primes. So find the largest powers of each prime that you can (which will be $2^4$, $3^3$ and $5^2$ added to each of the subsequent primes):

$$ 1 + 16 + 27 + 25 + 7 + 11 + 13 + 17 + 19 + 23 + 29 = 188 $$

There is no doubt that you should use $17$, $19$, $23$, and $29$. So then lets go down the list:

  • 13: $13 * 2 = 26$ is the only other factor possible. If you use that however we have to eliminate $16$ and $13$, so is $26 \stackrel{?}{>} 16 + 13$? No. So we're not going to use $26$.
  • 11: $11 * 2 = 22$ is the only other factor possible. If you use that however we have to eliminate $16$ and $13$, so is $22 \stackrel{?}{>} 16 + 11$? No. So we're not going to use $22$.
  • 7: We can do $4*7 = 28$ or $3*7 = 21$. If we choose $4*7 = 28$ then we eliminate $16$ and $7$, so is $28 \stackrel{?}{>} 7 + 16$? Yes. So that's a candidate. The next question is $21 \stackrel{?}{>} 27 + 7$? Clearly not...so we will use $28$ for $7$ and $2$ and not $21$ (for 7).

After that it's clear that we should use $5^2$ over $5$ and we have already eliminated $2^4$ by choosing $4*7$ over 16. This gives:

$$ 1+11+13+17+19+23+25+27+28+29=193 $$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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