You might be interested in the iota procedure.
I haven't programmed for a fairly long time, so I'm very rusty (I even forgot about named lets), but even when I did program regularly I always forgot about iota.
[member] is the part that holds back the speed. If you look at your final S, you will find that it grows roughly like the square root of R. But for each S jump test you are searching the entire R storage from the highest value downwards. You can tell exactly which R value will be hit by the next S jump and avoid searching entirely.
I sort of figured all that when I wrote it, I was just trying to write in the most stupid intuitive way possible to try to understand the sequence, and I guess for others to understand it. I might play the optimisation game, but I'll probably mostly play from the sidelines, lurking and what not. I have no where near the skills of you guys here, and I don't want to distract from the discussion. Anyway, this morning and last night I did write a more optimised version (still slow) I'd be willing to share, and cleaned up my original further, I was able to hit 10^7 on my machine in a reasonable time-frame.
The basic ideas were to reverse R keeping a pointer to the end, to remove values from the head of R once they've been used to construct S, and to stop growing R once it's clear the values won't be needed to construct S[n] (I still need to actually find when this is the case exactly).
;; clean
(define (hofstadter n)
(let H ((i (- n 1)) (R '(1)) (S 2))
(cond ((zero? i) (car R))
((member S R)
(H (- i 1) (cons (+ (car R) S 1) R) (+ S 2)))
(else (H (- i 1) (cons (+ (car R) S) R) (+ S 1))))))
;; faster
(define (hofstadter n)
(let ((r0 (list 1)))
(let H ((i (- n 1)) (r r0) (R r0) (S 1))
(letrec ((R! (lambda (n) (set-cdr! r (list (+ (car r) S n))))))
(cond ((zero? i) (car r))
((> (car r) (* n 2)) ; this is very conservative
(let E ((i i) (r (car r)) (R R) (S S))
(cond ((zero? i) r)
((= (car R) S)
(E (- i 1) (+ r S 1) (cdr R) (+ S 2)))
(else (E (- i 1) (+ r S) R (+ S 1))))))
((= (car R) S)
(begin (R! 1) (H (- i 1) (cdr r) (cdr R) (+ S 2))))
(else
(begin (R! 0) (H (- i 1) (cdr r) R (+ S 1)))))))))
(map (lambda (e) (hofstadter (expt 10 e))) (iota 8))
=> (1 69 5764 526334 50874761 5028514748 500918449417 50029364025646)
;; (1 69 5764 526334 50874761 5028514748 500918449417 50029364025646)