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

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Betting Game Rounds

Largest pairwise-coprime subset sum

Answer

Related questions