The Kitchen Sink and Other Oddities

Atabey Kaygun

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,Q(nQ(n1))+Q(nQ(n2)) for n3 It is not known if Q defines a total function. But it is known that for n1010, 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 n226

(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 O(n). So, if I wanted to push the 1010 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.