Hofstadter Figure-Figure Sequence

Define $F(1)=1$ and $S(1)=2$ and write

$$F(n)=F(n-1)+S(n-1),$$

where the sequence $\{S(n)\}$ consists of those integers not already contained in $\{F(n)\}$. For example, $F(2)=F(1)+S(1)=3$, so the next term of $S(n)$ is $S(2)=4$, giving $F(3)=F(2)+S(2)=7$. The next integer is 5, so $S(3)=5$ and $F(4)=F(3)+S(3)=12$. Continuing in this manner gives the ``figure'' sequence $F(n)$ as 1, 3, 7, 12, 18, 26, 35, 45, 56, ... (Sloane's A005228) and the ``space'' sequence as 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, ... (Sloane's A030124).

References

Hofstadter, D. R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, p. 73, 1989.

Sloane, N. J. A. Sequences A030124 and A005228/M2629 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.