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.
 A: 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.
A: 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
$$
