# maximize the sum of numbers such that all of them are coprime

Suppose we have numbers from $2$ to $n$ (inclusive). We want to choose numbers such that all of them are coprime and give the maximum sum.

For example, if $n=10$, then we choose $9,8,7,5$ and the sum is $29$. Note that we didn't choose $10,9,7$ since the sum is smaller than the former. I did this by trial and error. Is there an algorithm which gives me the numbers?

-
@BenjaminDickman: well, not really. take n=20. with your formula you get 5,7,9,11,13,16,17,19. But the maximal sum comes from 7,11,13,15,16,17,19 – neticin May 28 '14 at 12:00
Interesting; thanks for the counter-example. My original guess ("take maximal prime powers") is now deleted so as not to mislead. – Benjamin Dickman May 28 '14 at 12:05

Take all the primes from $2$ to $n$. The basic idea now is to substitute two numbers $a$ and $b$ by their product, provided that $ab\leq n$. Then, the sum increases $ab-a-b=(a-1)(b-1)+1$, formula which is crearly increasing respect to $a$ and $b$. So pick $n$. If it is not yet in the set and it can be expressed as a product of two members of the set, delete these two numbers and put $n$. Repeat with $n-1$, etc.
When you finish, begin again from $n$ to $2$, and repeat this until you can't make any more substitutions.