# Natural set to express any natural number as sum of two in the set

Any natural number can be expressed as the sum of three triangular numbers, or as four square numbers. The natural analog for expressing numbers as the sum of two others would apparently be the sum of two "linear" numbers, but all natural numbers are "linear", so this is rather unsatisfying. Is there a well-known sparser set of integers (or, half-integers, for that matter) that has this property?

-
Well, you could always take all the even numbers and $1$; or more generally, $k\mathbb{N}\cup\{1,2,\ldots,k-1\}$. Don't think they will be any more "satisfying", though. – Arturo Magidin Mar 7 '11 at 6:51
It's a start, but unfortunately, I don't find that too satisfying either. The triangular numbers have density 1/n, rather than constant density. – wnoise Mar 7 '11 at 7:19

Assuming Goldbach's conjecture, you can take the set of all primes and successors of primes (plus some small numbers). These have density $2/\log n$.
Not assuming the conjecture, you can take primes, almost-primes and successors of primes (plus some small numbers) - this is the famous Chen's theorem. The resulting density is $\log\log n/\log n$.
Another suggestion is to take the set of all numbers whose binary expansion is "supported" on only odd powers of $2$ or only even powers of $2$. The resulting density is roughly $2/\sqrt{n}$, so this is close to optimal (you need at least $1/\sqrt{n}$).