A Markov triple \((x,y,z)\in\mathbb{Z}^3\) is a solution to the Markov Diophantine equation
\[ x^2 + y^2 + z^2 = 3xyz \]
There is a very informative paper by Don Zagier on it that I recommend highly.
There are two singular solutions \((1,1,1)\) and \((1,1,2)\). Then we have the first non-singular one \((1,2,5)\). Strangely, given a non-trivial solution \((x,y,z)\) we have 3 (new) solutions:
Thus, we can place all of these solutions on a binary tree. Today, I am going to write lisp code that generates all Markov triples on this tree up to a certain depth.
(defun markov (depth)
(labels ((helper (x y z n)
(append (list (list x y z))
(if (> n 0)
(append (if (>= z x) (helper x z (- (* 3 x z) y) (1- n)))
(if (>= z y) (helper y z (- (* 3 y z) x) (1- n))))))))
(append (list '(1 1 1) '(1 1 2))
(helper 1 2 5 depth))))MARKOVLet us test:
(format nil "~{~A~%~}" (markov 5))(1 1 1)
(1 1 2)
(1 2 5)
(1 5 13)
(1 13 34)
(1 34 89)
(1 89 233)
(1 233 610)
(89 233 62210)
(34 89 9077)
(34 9077 925765)
(89 9077 2423525)
(13 34 1325)
(13 1325 51641)
(13 51641 2012674)
(1325 51641 205272962)
(34 1325 135137)
(34 135137 13782649)
(1325 135137 537169541)
(5 13 194)
(5 194 2897)
(5 2897 43261)
(5 43261 646018)
(2897 43261 375981346)
(194 2897 1686049)
(194 1686049 981277621)
(2897 1686049 14653451665)
(13 194 7561)
(13 7561 294685)
(13 294685 11485154)
(7561 294685 6684339842)
(194 7561 4400489)
(194 4400489 2561077037)
(7561 4400489 99816291793)
(2 5 29)
(2 29 169)
(2 169 985)
(2 985 5741)
(2 5741 33461)
(985 5741 16964653)
(169 985 499393)
(169 499393 253191266)
(985 499393 1475706146)
(29 169 14701)
(29 14701 1278818)
(29 1278818 111242465)
(14701 1278818 56399710225)
(169 14701 7453378)
(169 7453378 3778847945)
(14701 7453378 328716329765)
(5 29 433)
(5 433 6466)
(5 6466 96557)
(5 96557 1441889)
(6466 96557 1873012681)
(433 6466 8399329)
(433 8399329 10910721905)
(6466 8399329 162930183509)
(29 433 37666)
(29 37666 3276509)
(29 3276509 285018617)
(37666 3276509 370238963953)
(433 37666 48928105)
(433 48928105 63557570729)
(37666 48928105 5528778008357)