I wrote a first-order implementation based off of >>18 and my previous implementation >>95. I did end up deviating slightly in that I am computing R and taking the partial triangular number between every two values of R exclusive instead of doing the run-length encoding of S, so I thought it might be worth sharing:
;; first-order
(define (hofstadter n)
(let ((r0 (list 1))
(T (lambda (a b) (quotient (- (* b (- b 1)) (* a (+ a 1))) 2))))
(let H ((i 1) (r r0) (R r0) (R2 1) (S 1))
(let ((S1 (if (= (car R) S) (+ S 1) S)))
(if (> (+ i S1) n)
(+ R2 (T (car r) (+ (car r) (- n i) 1)))
(begin
(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))))))))I plan on copying and integrating the higher-order concept into this implementation, if I can.