Skip to content

Maximum sum of pairwise coprime numbers up to 30

Question

Among all subsets of {1,2,…,30}\{1,2,\dots,30\} in which every two elements are relatively prime, find the one whose elements add up to the most. What is that maximal sum?

Short answer

193. Start from 11 and all primes up to 3030 (sum 130130), then merge small primes into larger composite numbers built from them: 2,7→282,7\to28, 3→273\to27, 5→255\to25. Keeping 11, the primes from 1111 to 2929, and 25,27,2825,27,28 gives 193193, and an exhaustive search confirms nothing larger.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question