The answer is {11,13,17,19,23,25,27,28,29} with a sum of 192
The following greedy algorithm is NOT correct, though it's highly tempting to think it is:
- Arrange the numbers in descending order. This is "the list".
- Start with an empty set that will be the eventual answer. This is "the set".
- For each item on the list:
- If it has a common factor with any item in the set, discard it.
- Otherwise, add it to the set.
- Move to the next item in the list and go to step 4.
- When the list is empty, the set contains the solution to the problem.
A simple counter-example as a proof of incorrectness:
The numbers 2-10, run through the above algorithm, produce the set {10,9,7} with a sum of 26. The correct answer is {5,7,8,9} with a sum of 29.
A partial algorithm which is sufficient for the 2-30 case is as follows. This involves a list of possibilities created through elimination, and a list of probable elements to include created by construction.
Start with "possible list" containing all numbers you are concerned with.
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
For each prime in the list, locate its highest power that is in the list. In the 2-30 case, this gives 16,27,25,7,11,13,17,19,23,29. Remove these from the "possible list" and place them in the "probable list".
New lists:
2,3,4,5,6,8,9,10,12,14,15,18,20,21,22,24,26,28,30
7,11,13,16,17,19,23,25,27,29
3. For any number in the probable list that is non-prime (i.e. it is a square or greater power of a prime), eliminate from the possible list all multiples of the base prime smaller than that power. (Based on 16,27,25, remove 2,4,6,8,10,12,14,3,9,15,18,21,24,5,20 from the list of possibilities.)
New lists:
22,26,28,30
7,11,13,16,17,19,23,25,27,29
- For each number remaining in the possible list, compare it to the sum of the numbers in the probable list which share factors with it. If it is less than that sum, remove it from the possible list.
So:
22 < 11+16 so remove 22
26 < 13+16 so remove 26
28 > 7+16 so leave it alone
30 < 16+27+25 so remove 30
New lists:
28
7,11,13,16,17,19,23,25,27,29
- In this case it is simple as there is only one left in the possibile list and it is greater than the prime powers it will replace, so it is put in the probable list, displacing 7 and 16, and that is the end of it. For much larger numbers, I haven't developed the algorithm.
Best Answer
If $l$ is a prime that divides $F_n$, then $2^{2^n}\equiv -1 \pmod{l}$, and therefore $2^{2^{n+1}}\equiv 1 \pmod{l}$. So $2$ has order $2^{n+1}$ modulo $l$. Equivalently, but in more group-theoretic language, (the equivalence class of) $2$ has order $2^{n+1}$ in $(\mathbb{Z}/l\mathbb{Z})^\times$. (The order of $2$ must divide $2^{n+1}$, but cannot be $\le 2^n$.)
If $p$ is a prime that divides $2^{2^k}+1$, then by the same reasoning $2$ has order $2^{k+1}$ modulo $p$. If $k<n$, that means that $p$ cannot be equal to $l$. So we have proved that no prime that divides $F_n$ can divide any $F_k$ with $k<n$. This shows that $F_n$ and $F_k$ are relatively prime.
Remark: We do not really need to identify the order of $2$ explicitly. For if $l$ is a prime that divides $F_n$, then $2^{2^n}\equiv -1 \pmod{l}$. But if $p$ is a prime that divides $F_k$ for some $k<n$, then $2^{2^k}\equiv -1\pmod{p}$, and therefore $2^{2^{k+1}}\equiv 1\pmod{p}$. Since $k+1 \le n$, this is impossible.