The error term in Golomb's sequence (Q1185813)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The error term in Golomb's sequence |
scientific article |
Statements
The error term in Golomb's sequence (English)
0 references
28 June 1992
0 references
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.
0 references
Golomb sequence
0 references
self-describing sequence
0 references
enumeration of trees
0 references
asymptotic formula
0 references
error term
0 references