Here is my attempt at an ``understandability golf'' of the hofstadter sequence. It was naively created by using a table of indices, and values to look for patterns. The program is more or less a direct encoding of the table. The key to this sequence is to understand that the rate of change is incremental with a skip every once in a while, such as on iterations 1, 4, 8, and 13. The rate of change of these skips is incremental, the gap between them increasing by one after every skip. This implementation is one of the slower implementations here and simply linear, it starts to really chug around i = 10^8 on my poor machine.
| i | n | d | d2 | d3 |
|---+----+----+----+----|
| 0 | 1 | 1 | 1 | 3 |
| 1 | 3 | 2 | 1 | 3 |
| 2 | 7 | 4 | 4 | 4 |
| 3 | 12 | 5 | 4 | 4 |
| 4 | 18 | 6 | 4 | 4 |
| 5 | 26 | 8 | 8 | 5 |
| 6 | 35 | 9 | 8 | 5 |
| 7 | 45 | 10 | 8 | 5 |
| 8 | 56 | 11 | 8 | 5 |
| 9 | 69 | 13 | 13 | 6 |(define (hofstadter nth)
(letrec ((I (lambda (i d d2 d3 n)
(cond ((= i nth) n)
((= i d2)
(I (+ i 1) (+ d 2) (+ d2 d3) (+ d3 1) (+ n d 2)))
(else (I (+ i 1) (+ d 1) d2 d3 (+ n d 1)))))))
(I 0 1 1 3 1)))
(map hofstadter '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19))
=> (1 3 7 12 18 26 35 45 56 69 83 98 114 131 150 170 191 213 236 260)
(hofstadter (expt 10 8))
=> 5000942759072091