Hofstadter sequences

Example

Hofstadter sequences are integer sequences defined by nested nonlinear recurrences, in which earlier values decide which earlier terms are used.

1. The Hofstadter $Q$-sequence is given by $Q(1) = Q(2) = 1$ and $Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))$ for $n > 2$. It begins $1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, \dots$.
2. The Hofstadter $G$-sequence is given by $G(0) = 0$ and $G(n) = n - G(G(n-1))$ for $n \ge 1$. It begins $0, 1, 1, 2, 3, 3, 4, 4, 5, \dots$.

Check for $Q$: $Q(3) = Q(2) + Q(2) = 2$, $Q(4) = Q(2) + Q(3) = 3$, $Q(5) = Q(2) + Q(3) = 3$, $Q(6) = Q(3) + Q(3) = 4$. Check for $G$: $G(1) = 1 - G(0) = 1$, $G(2) = 2 - G(1) = 1$, $G(3) = 3 - G(1) = 2$, $G(4) = 4 - G(2) = 3$. The $G$-sequence has the closed form $G(n) = \lfloor (n+1)/\varphi \rfloor$, where $\varphi$ is the golden ratio. The $Q$-sequence behaves erratically, and it is not known whether it is defined for all $n$, that is, whether $n - Q(n-1) \ge 1$ and $n - Q(n-2) \ge 1$ always hold.