The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Abstract

Let $(a_n{)}_{n\ge 1}$ be the greedy self-generating sequence defined by $a_1=1$, $a_2=2$, and, for $k\ge 3$, by taking $a_k$ to be the least integer greater than $a_{k-1}$ that can be written as a sum of at least two consecutive earlier terms. Hofstadter asked about the asymptotic behavior of this sequence. In this paper we prove that $$n+\Omega (\log \log n)\le a_n\ll n^{4175/2506+o(1)}.$$ In particular, $(a_n{)}_{n\ge 1}$ omits infinitely many positive integers, thereby settling a conjecture from the OEIS entry A005243.

arXiv comment16 pages, 1 figure. This is the submitted version