Hofstadter G-sequence

Hofstadter G-sequence
(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 -> 0, 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)))))

A tabela dos 10 primeiros termos da sequência de Hofstadter obtida com a instrução é (table-Hofstadter-G-sequence 10) é

0 0
1 1
2 1
3 2
4 3
5 3
6 4
7 4
8 5
9 6
10 6
nil

Um cálculo mais exaustivo com 10000 termos está aqui.

Refs:

Palavras chave: Hofstadter G-sequence, OEIS A005206, Lisp, Emacs

Última actualização/Last updated: 2012-02-26 [15:48]

1999-2011 (c) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.