Hofstadter-Conway $10,000 sequence

Description of the problem

Consider the recursively defined sequence of integers:

a(1) = 1
a(2) = 1
a(n) = a(a(n-1)) + a(n-a(n-1))

This is called Hofstadter-Conway $10,000 sequence. Originally, the challenge was to find \(p\) such that \(a(n)/n\>0.55\) for every \(p\geq n\). But we are going to find \(p\) such that \(a(n)/n\>0.55\) for every \(2^{23}\>n\>p\).

An implementation for the solution

First, I am going to need a function which generates the values of the sequence. I am going to memoize the computation using a hash table:

(let ((lookup (make-hash-table)))
  (defun seq(n)
    (if (or (= n 1) (= n 2))
        1
        (or (gethash n lookup)
            (setf (gethash n lookup)
                  (+ (seq (seq (1- n)))
                     (seq (- n (seq (1- n))))))))))
SEQ

Next is a function that calculates the maximum of the sequence \(a(n)/n\) between two consecutive power of 2:

(defun test (n)
  (let* ((a (expt 2 n))
         (b (* a 2)))
    (do* ((i a (1+ i))
          (j (/ (seq i) i 1.0) (/ (seq i) i 1.0))
          (l a (if (> j m) i l))
          (m j (max m j)))
         ((= i b) (cons m l)))))
TEST

Let us see how this works:

(loop for i from 2 to 23 collect
   (test i))
((0.6666667 . 6) (0.6363636 . 11) (0.6086956 . 23) (0.59090906 . 44)
 (0.57608694 . 92) (0.5674157 . 178) (0.55945945 . 370) (0.5549374 . 719)
 (0.55010086 . 1487) (0.5474629 . 2897) (0.54414475 . 5969)
 (0.5424427 . 11651) (0.54007107 . 22223) (0.538784 . 45083)
 (0.53704363 . 89516) (0.53602004 . 181385) (0.53464544 . 353683)
 (0.5337792 . 722589) (0.53267705 . 1423078) (0.5319232 . 2903564)
 (0.53101355 . 5696576) (0.53034115 . 11635313))

Next, let us solve the challenge for numbers less than \(2^{23}\)

(defun marrow (n)
   (do ((i (expt 2 n) (1- i)))
       ((> (/ (seq i) i 1.0) 0.55) i)))
MARROW

(marrow 23)
1489