Hofstadter Figure-Figure Sequence

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


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, ... (OEIS A005228) and the "space" sequence as 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, ... (OEIS A030124).

Explore with Wolfram|Alpha


Hofstadter, D. R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, p. 73, 1989.Sloane, N. J. A. Sequences A005228/M2629 and A030124 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Hofstadter Figure-Figure Sequence

Cite this as:

Weisstein, Eric W. "Hofstadter Figure-Figure Sequence." From MathWorld--A Wolfram Web Resource.

Subject classifications