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\).
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))))))))))
SEQNext 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)))))
TESTLet 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