A diluted version of the problem of the existence of the Hofstadter sequence
Jonathan H. B. Deane, Guido Gentile · The Journal of Difference Equations and Applications · 2024
We investigate the conditions on an integer sequence f(n), n∈N, with f(1)=0, such that the sequence q(n), computed recursively via q(n)=q(n−q(n−1))+f(n), with q(1)=1, exists. We prove that f(n) is ‘slow’, that is, f(n+1)−f(n)∈{0,1}, n≥1, is a sufficient but not necessary condition for the existence of sequence q. Sequences q defined in this way typically display non-trivial dynamics: in particular, they are generally aperiodic with no obvious patterns. We discuss and illustrate this behavior with some examples.