Hofstadter's Q sequence

Description of the problem:

Third in my series of interesting recursive sequences, today I am going to look at Hofstadter’s Q sequence. It is defined recursively as \[ Q(1) = Q(2) = 1, \qquad Q(n - Q(n-1)) + Q(n - Q(n-2)) \text{ for } n\geq 3 \] It is not known if \(Q\) defines a total function. But it is known that for \(n\leq 10^{10}\), the values \(Q(n)\) are all defined.

Implementation

A straight-forward recursive implementation would blow the stack. So, I am going to use memoization again:

(let ((table (make-hash-table)))
  (defun hofstadter (n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (t (or (gethash n table)
                 (setf (gethash n table)
                       (+ (hofstadter (- n (hofstadter (- n 1))))
                          (hofstadter (- n (hofstadter (- n 2)))))))))))

HOFSTADTER

Let us test our function on all values of \(n\leq 2^{26}\)

(time (let ()
         (loop for i from 1 to (expt 2 26) collect (hofstadter i))  
         nil))

Evaluation took:
  65.256 seconds of real time
  65.256000 seconds of total run time (64.240000 user, 1.016000 system)
  [ Run times consist of 1.796 seconds GC time, and 63.460 seconds non-GC time. ]
  100.00% CPU
  169,141,552,764 processor cycles
  6,442,594,400 bytes consed

NIL

An analysis

With memoization, the time complexity appears to be \(\mathcal{O}(n)\). So, if I wanted to push the \(10^{10}\) limit, I would have to wait about an hour on my laptop at work, provided I do not blow the dynamic space sbcl reserves for the computation. I should probably not collect the result since they all are recorded on table already.