Hofstadter G-Sequence

Author

Eric W. Weisstein
September 14, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/HofstadterG-Sequence.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/HofstadterG-Sequence.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Sequence

RSolve[{G[n]==n-G[G[n-1]],G[0]==0},G[n],n]

G[0]:=0
G[n_]:=G[n]=n-G[G[n-1]]

G/@Range[20]

Formulas

⌊(n+1) ϕ⌋-n-1

Table[Floor[(n+1)GoldenRatio]-n-1,{n,20}]

⌊((n+1)/ϕ)⌋

Table[Floor[(n+1)/GoldenRatio],{n,20}]

FullSimplify[Floor[(n+1)/GoldenRatio]-(Floor[(n+1)GoldenRatio]-n-1),n∈Integers]

Table[Floor[(n+1)/GoldenRatio]-(Floor[(n+1)GoldenRatio]-n-1),{n,-5,5}]

a(n)=n-a(⌊(n/ϕ)⌋)

a[0]:=0
a[1]:=1
a[n_]:=a[n]=n-a[Floor[n/GoldenRatio]]

a/@Range[20]