The error term in Golomb's sequence

AbstractS. Golomb discovered a self describing sequence of integers with a simple asymptotic behavior. This paper examines how close the sequence is to the asymptotic estimate. I give an upper bound for the error term and give strong evidence that this upper bound is actually the best possible. The evidence consists of a formal solution to a recurrence relation, as well as numerical evidence. I also present an efficient method for computing Golomb's sequence for large values. This method relies on the enumeration of a special kind of tree