Generating Markov number sequence with python

Question

I wanted to do something to get a better understanding of yield and yield from. The goal is to generate the markov sequence in order, with the first element being index 0. https://en.wikipedia.org/wiki/Markov_number

I came up with the following code.

def chain(iter1, iter2):
    while True:
        yield next(iter1)
        yield next(iter2)

def isMarkov(x,y,z):
    if x**2 + y**2 + z**2 == 3 * x * y * z:
        return True
    else:
        return False

def gen_markov(seed):
    x1 = seed[0]
    y1 = seed[2]
    z1 = y1 + 1
    while not isMarkov(x1,y1,z1):
        z1 += 1
    yield (x1,y1,z1)
    
    x2 = seed[1]
    y2 = seed[2]
    z2 = y2 + 1
    while not isMarkov(x2,y2,z2):
        z2 += 1
    yield (x2,y2,z2)
    
    yield from chain(gen_markov((x1,y1,z1)), gen_markov((x2,y2,z2)))
    
def markov(n):
    g = gen_markov((1,2,5))
    markov_nums = set([1,2,5])
    while len(markov_nums) <= n:
        triple = next(g)
        for x in triple:
            markov_nums.add(x)
    markov_nums = list(markov_nums)
    markov_nums.sort()
    print(markov_nums[n])

n = int(input('Enter n: '))
markov(n)

This can generate markov triples in a tree like structure.

Heres the first 35 markov triples generated by the gen_markov function.

(1, 5, 13)
(2, 5, 29)
(1, 13, 34)
(2, 29, 169)
(5, 13, 194)
(5, 29, 433)
(1, 34, 89)
(2, 169, 985)
(5, 194, 2897)
(5, 433, 6466)
(13, 34, 1325)
(29, 169, 14701)
(13, 194, 7561)
(29, 433, 37666)
(1, 89, 233)
(2, 985, 5741)
(5, 2897, 43261)
(5, 6466, 96557)
(13, 1325, 51641)
(29, 14701, 1278818)
(13, 7561, 294685)
(29, 37666, 3276509)
(34, 89, 9077)
(169, 985, 499393)
(194, 2897, 1686049)
(433, 6466, 8399329)
(34, 1325, 135137)
(169, 14701, 7453378)
(194, 7561, 4400489)
(433, 37666, 48928105)
(1, 233, 610)
(2, 5741, 33461)
(5, 43261, 646018)
(5, 96557, 1441889)
(13, 51641, 2012674)

My issue is that I want to be able to generate the sequence in order. The number 610 is the 11th element in the sequence, but numbers far greater than 610 are generated earlier. For instance, if you run for n=11 the function returns 2897. Any advice on how to generate the sequence in order?

user_16462878 · Answer

This is my contribution (not an answer) to this question, I completely re-edit my first attempt, and I will not go any further. Why? The question is not well-defined:

the wikipedia article you suggest as reference is terrible (see also my comments)
you haven't specified the ordering rule & the definition of Markov number [I documented myself, also with technical/research papers, but haven't found anything (not even a proper definition of Markov number!!)]

So, as long you will not improve the question such that it is accessible to everyone I will consider it as close.

Suggestions

ask to the math stackexchange community on how to generate an ordered Markov sequence
before the yield/yield from implementation you should have a working example and an understanding of it(?), i.e. in this case choose another (easier) problem to start with!
provide more information of the problem

Consideration

Markov numbers are nodes of a binary tree, so implement a binary tree
each level of the tree has two (relative) minimum, the most external leaves, which are described by the Fibonacci and Pell sequence. The Fibonacci is the smallest one. These could be used as break-condition on the size of a list containing the n-Markov numbers
by keeping it easy, use a greedy algorithm... if you want a list of n-ordered Markov numbers, for example, consider a perfect binary tree (it is computational expensive, size modeled by a geometric series with initial value 1 and common ratio 2) and sorted them by increasing order and consider the 1st n-entries of such list, smt like

list(sorted(markov_triples, key=lambda p: p[1]))[:n]

Danger as mentioned in a comment, in the wikipedia article the nodes corresponding to the Markov number 194 are not labeled correctly, see my comment for a reference. Here a more detailed Markov tree than the one of wikipedia.

A sample code concerning the computation of a leaf of the tree. I use as reference a perfect tree which nodes can be uniquely described as terms of a geometric sequence to locate the leaf then find the sequence of left and right path which lead to the root and finally apply the "Markov rules" to find the triples:

from math import log

def find_lv(n): # provided that the root as vertex 1, n: absolute node index
    return int(log(n, 2))

def branch_path(n, k): # leaf to root
    # n: depth, k: 0 <= index <= 2**n - 1
    path = [k]
    for i in range(n-1):
        if path[-1] % 2 == 0:
            path += [path[-1] // 2]
        else:
            path += [path[-1] // 2]
    return path

def branch_path_as_directions(path): # leaf to root
    return ['L' if p % 2 == 0 else 'R' for p in path[:-1]] # the root should be skiped!

def new_sol(triple):
    x, y, z = triple
    return (x, y, 3*x*y - z)

def left_triple(triple): 
    x, y, z = triple
    return (x, z, y)

def right_triple(triple): 
    x, y, z = triple
    return (y, z, x)

def markov_triples(n):
   # n: is the absolute position of a node in the tree, i.e. wrt to a geometric series
   # return the branch of triples corresponding to that node
    # initial values of the sequence
    triples = [(1, 1, 1), (1, 1, 2), (1, 2, 5)]
    if n == -2:
        return triples[0]
    if n == -1:
        return triples[1]
    if n == 0:
        return triples[2]

    depth = find_lv(n) + 1

    # get path the leaf with n
    path = branch_path(depth, n)
    path_l_r = branch_path_as_directions(path)
        
    # flow from root to leaf
    for direction in path_l_r[::-1]:
        if direction == 'L':
            triples += [new_sol(left_triple(triples[-1]))]
        else:
            triples += [new_sol(right_triple(triples[-1]))]
            
    return triples

print(markov_triples(10))

Output

[(1, 2, 5), (1, 5, 13), (5, 13, 194), (5, 194, 2897)]

user_4880945 · Answer

Update. I was able to find a reasonably better solution using a queue (although not perfect).

# Markov Numbers

seed = (1,2,5)
markov = set()
markov.add(1)
queue = []
queue.append(seed)

n = int(input('Enter n: '))

while len(markov) <= n**3:
    curr = queue.pop()
    p,q,r = (curr)
    markov.add(p)
    markov.add(q)
    markov.add(r)
    left = (p,r,3*p*r-q)
    right = (q,r,3*q*r-p)
    queue.insert(0,left)
    queue.insert(0,right)
markov = list(markov)
markov.sort()
print(markov[n])

I tested this up to n=39, (starting from index 0). This matches up with the first 40 elements in the OEIS. https://oeis.org/A002559/list

0th element: 1
1th element: 2
2th element: 5
3th element: 13
4th element: 29
5th element: 34
6th element: 89
7th element: 169
8th element: 194
9th element: 233
10th element: 433
11th element: 610
12th element: 985
13th element: 1325
14th element: 1597
15th element: 2897
16th element: 4181
17th element: 5741
18th element: 6466
19th element: 7561
20th element: 9077
21th element: 10946
22th element: 14701
23th element: 28657
24th element: 33461
25th element: 37666
26th element: 43261
27th element: 51641
28th element: 62210
29th element: 75025
30th element: 96557
31th element: 135137
32th element: 195025
33th element: 196418
34th element: 294685
35th element: 426389
36th element: 499393
37th element: 514229
38th element: 646018
39th element: 925765

This isn't perfect because it's still necessary to search much farther than n to get an accurate result for around n>10. That is why there is the n**3 term. If anyone could explain a better method it would be appreciated.

Generating Markov number sequence with python

2 Answers