A wordy explanation for the less mathematically inclined*
*
warning: this problem is mathematical, numbers will be involved
The population of Barberland can be represented as a list of numbers.
A number can't appear on the list more than once, can't be greater than 1000000 or less than 0 (we'll assume than having a negative number of hairs is impossible but having zero is allowed), and no number in the list can be the sum of 2 other numbers in the list.
Zero can be included in any list without requiring any other numbers to be excluded because "Nobody in Barberland has the same number of hairs as the sum of two other inhabitants"
If we include the numbers 1 and 2 then the number 3 must be excluded. We could then include 4 but that would exclude 5 and 6. If we then included 7 that would exclude 8, 9 and 11. 10 would be okay to include (we don't have a pair of numbers that sum to 10) but that then excludes 11, 12, 14 and 17 because we have already selected 1,2,4 and 7.
This naive method of selecting numbers generates the Stöhr Sequence A033627 and results in approximately 1/3 of the numbers in a range being selected.
If we continue with this method of choosing numbers to include in the list, each one excludes more of the higher numbers. It really isn't a good way to approach the problem but does demonstrate the what happens if you try to include small numbers in the list.
By including 1 in the list you have effectively ruled out half of all possible numbers, as each other number you include would exclude 1 plus that number. If you were to start with 1 you could then pick only odd numbers all the way to 999999 because 2 odd numbers always sum to an even number.
Using only zero and odd numbers would result in a list of length 500001 (500000 odd numbers + 1 zero), approximately 1/2 of the numbers in the range being selected.
Working down from 1000000 is more effective. The sum of pairs of the largest numbers, are greater than 1000000, and so are not excluding any available options. This is true all the way down to 500000.
When we get to 499999 we can't include it without invalidating either 500000 or 999999. The smaller the number gets past 500000 the more larger numbers it invalidates in a way resembles the problems encountered when starting with small numbers.
Using the numbers zero and 500000 to 100000 results in a list of length 500002, slightly better than than the odd numbers method and significantly better than the naive method.