Largest pairwise-coprime subset sum

HardCombinatorics Brainteasers~10m

Consider subsets of $S = \{1, 2, 3, \dots, 30\}$ in which every pair of elements is coprime. Among all such subsets, find the one whose elements have the largest possible sum, and give that sum.

Show hints (2)+

$1$ is free; each prime $\le30$ may divide at most one chosen number. Prefer large prime powers.
$\{1,11,13,17,19,23,25,27,28,29\}$ - with $27,25,28$ monopolizing $3,5,2,7$ - sums to $193$ .

Answer

Reveal answer →

193

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, SIG

Largest pairwise-coprime subset sum

Answer

Related questions