"David Wilson" <davidwwilson@attbi.com> writes:

Here's another idea to consider:

Each Ulam number u(n), n >= 2 (zero index) is a unique sum a(n) + b(n) of distinct earlier Ulam numbers a(n) < b(n). Tabulate a(n) for 2 <= n <= 2000. There are only 47 distinct values of a(n). It seems like certain Ulams, starting with 2, 3, 47, 69, etc, are much more likely to be involved in the sums for subsequent Ulams.

Presumably the ones that appear often are the ones in the "sparse space". But something's off with the definition, since your observation would imply that 1, 2, and 3 were all in S, and so the whole sequence would be in S. So I suspect that one of {2,3} will die out as a common addend, and the other will be in the sparse space. Or maybe I need to rejigger the sparse space analysis. If a sparse space can be found that has only finitely many elements of the sequence in it, the sequence can be generated in linear time instead of quadratic. Dan