TOPICS
Search

Hofstadter G-Sequence


The sequence defined by G(0)=0 and

 G(n)=n-G(G(n-1)).
(1)

The first few terms for n=1, 2, ... are 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, ... (OEIS A005206).

This can be written as a simple recurrence relation

 G(n)=n-G(|_nphi^(-1)_|)
(2)

with G(0)=0 and G(1)=1 and where |_x_| is the floor function and phi the golden ratio.

Closed forms include

G(n)=|_(n+1)phi_|-n-1
(3)
=|_(n+1)/phi_|.
(4)

Explore with Wolfram|Alpha

References

Gault, D. and Clint, M. "'Curiouser and Curiouser,' Said Alice. Further Reflections on an Interesting Recursive Function." Internat. J. Computer Math. 26, 35-43, 1988.Gould, H. W.; Kim, J. B.; and Hoggatt, V. E. Jr. "Sequences Associated with T-Ary Coding of Fibonacci's Rabbits." Fib. Quart. 15, 311-318, 1977.Granville, V. and Rasson, J. P. "A Strange Recursive Relation." J. Number Th. 30, 238-241, 1988.Grytczuk, J. "Another Variation on Conway's Recursive Sequence." Discr. Math. 282, 149-161, 2004.Hofstadter, D. R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, p. 137, 1989.Sloane, N. J. A. Sequence A005206/M0436 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Hofstadter G-Sequence

Cite this as:

Weisstein, Eric W. "Hofstadter G-Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HofstadterG-Sequence.html

Subject classifications