# Largest Arithmetic Sum of Relatively Prime Numbers Under 30

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
• @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

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$$