On Golomb's self-describing sequence (Q1366666): Difference between revisions

The self-describing Golomb sequence \((F(n))_{n\geq 1}\) [see \textit{S. W. Golomb}, Problem 5407, Am. Math. Mon. 73, 674 (1966)] is defined by \(F(1)=1\) and \(F(n)= \#\{m;\;F(m)=n\}\) and the condition \(F\) increasing. Fine proved that \(F(n)= cn^{\varphi-1}+ E(n)\), with \(\varphi= \frac{1+\sqrt{5}}{2}\), \(c=\varphi^{2-\varphi}\) and \(E(n)= o(n^{\varphi-1})\) [\textit{N. J. Fine}, Solution to problem 5407, Am. Math. Mon. 74, 740-743 (1967)]. Vardi proved that \(E(n)= O(\frac{n^{\varphi-1}}{\log n})\) and conjectured that \[ E(n)= \Omega_\pm \Biggl(\frac{n^{\varphi-1}} {\log n}\Biggr) \] [\textit{I. Vardi}, J. Number Theory 40, 1-11 (1992; Zbl 0758.11012)]. After \textit{Y.-F. S. Pétermann}'s result [J. Number Theory 53, 13-24 (1995; Zbl 0839.11005)]: \(E(n)= \Omega_\pm (n^{\varphi-1- \varepsilon})\), \(\forall \varepsilon>0\), the paper under review proves Vardi's conjecture. The author first gives an experimental approach, then an intuitive proof. The paper culminates with the proof itself.