An erratic two-dimensional recursive function Q2
14th March 2020
I have been looking for interesting recursive functions to use as a benchmark for different implementations of languages such as my Lisp interpreter, uLisp. My search has taken me from the Fibonacci function, Pascal's triangle, and the Hofstadter Q sequence, to a new erratic two-dimensional function I've called Q2.
Two-dimensional Fibonacci function
I started by thinking about how to make a two-dimensional version of the Fibonacci function. The number at coordinates (x, y) would be the sum of the two numbers at (x-1, y) and (x, y-1). Here's the function, which I've called fib2:
(defun fib2 (x y)
(if (or (< x 1) (< y 1)) 1
(+ (fib2 (1- x) y) (fib2 x (1- y)))))
Here's fib2 solved for values of x and y from 0 to 11, with (0, 0) at the bottom left corner:
1 11 66 286 1001 3003 8008 19448 43758 92378 184756 1 10 55 220 715 2002 5005 11440 24310 48620 92378 1 9 45 165 495 1287 3003 6435 12870 24310 43758 1 8 36 120 330 792 1716 3432 6435 11440 19448 1 7 28 84 210 462 924 1716 3003 5005 8008 1 6 21 56 126 252 462 792 1287 2002 3003 1 5 15 35 70 126 210 330 495 715 1001 1 4 10 20 35 56 84 120 165 220 286 1 3 6 10 15 21 28 36 45 55 66 1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 1 1 1 1 1 1
It soon dawned on me that fib2 is just Pascal's triangle, so the number fib2(x, y) is the number of combinations of n things taken k at a time, or nCk, where n = x + y and k = x.
Hofstadter Q sequence
One of my favourite recursive functions is the Hofstadter Q sequence, one of several recursive sequences described in Douglas Hofstadter's brilliant book "Gödel, Escher, Bach: an Eternal Golden Braid". It is defined as follows:
(defun q (n)
(if (<= n 2) 1
(+
(q (- n (q (- n 1))))
(q (- n (q (- n 2)))))))
It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed. The intriguing thing about it is that its behaviour is quite erratic; for example, q(14) = 8, q(15) = 10, and q(16) = 9.
Two-dimensional function Q2
I thought about whether one could combine Pascal's triangle with the double recursion used in Hofstadter's Q sequence. So the value at (x, y) would be the sum of two values, found by going back (x-1, y) in the x direction, and (x, y-1) in the y direction. Here's the function which I've called Q2:
(defun q2 (x y)
(if (or (< x 1) (< y 1)) 1
(+ (q2 (- x (q2 (1- x) y)) y)
(q2 x (- y (q2 x (1- y)))))))
It has beautifully erratic behaviour; here's the function for values of x and y from 0 to 15, with (0, 0) at the bottom left corner:
1 6 6 6 6 2 42 2 170 2 497 2 1200 2 2541 2 1 5 5 6 10 15 2 85 2 262 2 638 2 1341 2 2541 1 5 5 6 3 6 36 2 128 2 327 2 703 2 1341 2 1 5 5 4 5 20 2 70 2 177 2 376 2 703 2 1200 1 5 5 5 9 2 35 2 92 2 199 2 376 2 638 2 1 5 5 5 4 19 2 50 2 107 2 199 2 327 2 497 1 4 4 5 9 2 26 2 57 2 107 2 177 2 262 2 1 4 4 5 2 14 2 31 2 57 2 92 2 128 2 170 1 4 4 3 8 2 17 2 31 2 50 2 70 2 85 2 1 4 4 4 4 9 2 17 2 26 2 35 2 36 2 42 1 3 3 4 5 2 9 2 14 2 19 2 20 6 15 2 1 3 3 4 2 5 4 8 2 9 4 9 5 3 10 6 1 3 3 2 4 4 4 3 5 5 5 5 4 6 6 6 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
It's such a simple function I can't believe it hasn't been discussed before; if anyone can find a reference please let me know.
Benchmarks
It's a time-consuming function to calculate (without memoization). Here are some benchmarks for calculating Q2(14, 15) = 2514:
- LispWorks running on a 2.8 GHz MacBook Pro: 137 secs.
- SBCL running on a 2.8 GHz MacBook Pro: 213 secs.
How does your version of Lisp fare?
Unsolved problems
Obviously Q2(x, y) = Q2(y, x). However, the function raises several interesting questions:
- Is Q2(x, y) always 2 when x = y?
- Is Q2(x+1, y+1) always larger than Q2(x, y) when x and y differ by 1?
- Is there an explicit formula for Q2(x, y)?
Footnote: printing the function
Here's the program I used to print out the function values:
(defun test (size)
(let (a)
(dotimes (x size a)
(let (b)
(push (dotimes (y size (reverse b)) (push (q2 x y) b)) a)))
(format t "~{~{~5a~}~%~}" a)))
blog comments powered by Disqus