Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
@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.

Warning: I have made no proofs, so I'm not completely sure that this process actually gives the maximum sum.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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