Tiago Charters work gallery about blog contact

(defun G (n)
  "Emacs Lisp function
for OEIS sequence number A005206.
Hofstadter G-sequence: a(n) = n - a(a(n-1)),
where
a(n)=floor((n+1)*tau)-n-1 where tau=(1+sqrt(5))/2;
a(0)=0, a(1)=1, a(n)=n-a(floor(n/tau))
or
phi=(1+sqrt(5))/2
G(n)=(n=0 -> 1, n=1 -> 1, t -> n-G([n/phi]))"
  (let ((phi (/ (+ 1 (sqrt 5)) 2)))
    (cond ((eq n 0) 0)
          ((eq n 1) 1)
          (t (- n (G (floor (/ n phi))))))))

(defun table-Hofstadter-G-sequence (n)
"Table of k, G(k) for k=0...n"
  (let ((k 0))
    (while (<= k n)
      (princ k )
      (princ " ")
      (princ (G k))
      (princ "\n")
      (setq k (+  1 k)))))

---

For attribution, please cite this page as:

Charters, T., "Hofstadter G-sequence": https://nexp.pt/hofstadter.html (16-02-2026 [16:02])

---

(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt