>>125
Here is my improved version, I took the group number directly from >>23 and keep only those values of R necessary to generate S[n] for the first order R just as I did with my second implementation >>95. My timings are still shifted one below that of flake.hofs, and I'm not still not sure why.
(define (hofstadter n)
(let ((r0 (list 1))
(T (lambda (a b) (quotient (- (* b (- b 1)) (* a (+ a 1))) 2)))
(m (inexact->exact (ceiling (* 1.5 (sqrt n))))))
(let H ((i 1) (r r0) (R r0) (R2 1) (S 1))
(let ((S1 (if (= (car R) S) (+ S 1) S)))
(cond ((> (+ i S1) n) (+ R2 (T (car r) (+ (car r) (- n i) 1))))
((>= (car r) m)
(let E ((i i) (r (car r)) (R R) (R2 R2) (S S))
(let ((S1 (if (= (car R) S) (+ S 1) S)))
(if (> (+ i S1) n)
(+ R2 (T r (+ r (- n i) 1)))
(E (+ i (- S1 1)) (+ r S1)
(if (= (car R) S) (cdr R) R)
(+ R2 (T r (+ r S1))) (+ S1 1))))))
(else (set-cdr! r (list (+ (car r) S1)))
(H (+ i (- S1 1)) (cdr r) (if (= (car R) S) (cdr R) R)
(+ R2 (T (car r) (cadr r))) (+ S1 1))))))))