Largest Arithmetic Sum of Relatively Prime Numbers Under 30

Question

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.

Answer 1

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.

Answer 2

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