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.
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)))))))))))HOFSTADTERLet 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
NILWith 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.