The error term in Golomb's sequence (Q1185813)

S. Golomb has defined a sequence of integers \((F(n))_ n\) by \(F(1)=1\), \(F(n)=\#\{m\); \(F(m)=n\}\) and \(F\) is nondecreasing, so that \[ (F(n))_ n=1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,\dots\;. \] He asked for an asymptotic formula for \(F\), and it has been proved that \(F(n)\sim cn^{\varphi-1}\), where \(c=\varphi^{2-\varphi}\), and \(\varphi\) is the golden ratio. The main result of this paper is an estimation of the error term (which answers a question of Knuth). The author proves \[ E(n)=F(n)- cn^{\varphi-1}=O\left({n^{\varphi-1}\over {\log n}}\right). \] Although this estimation does not seem sharp in view of numerical computations by Knuth (showing that \(E(n)\leq .51\) for \(n\leq 400\)) the author conjectures that \[ E(n)=\Omega_ \pm\left( {n^{\varphi-1} \over {\log n}}\right), \] and even gives a stronger conjecture. In the last part of the paper the author shows how to compute \(F(n)\) for large values of \(n\), using the enumeration of a special kind of trees.