Блог

Я хотел сделать что-то, чтобы лучше понять доходность и доходность. Цель состоит в том, чтобы сгенерировать последовательность Маркова по порядку, при этом первым элементом будет индекс 0. https://en.wikipedia.org/wiki/Markov_number

Я придумал следующий код.

 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)
 

Это может генерировать тройки Маркова в древовидной структуре.

Вот первые 35 марковских троек, сгенерированных функцией gen_markov.

 (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)
 

Моя проблема в том, что я хочу иметь возможность генерировать последовательность по порядку. Число 610 является 11-м элементом в последовательности, но числа, намного превышающие 610, генерируются раньше. Например, если вы выполняете для n=11, функция возвращает 2897. Есть какие-нибудь советы о том, как сгенерировать последовательность по порядку?

Это мой вклад (а не ответ) на этот вопрос, я полностью отредактировал свою первую попытку и не буду идти дальше. Почему? Этот вопрос не имеет четкого определения:

1. статья в Википедии, которую вы предлагаете в качестве ссылки, ужасна (см. Также мои комментарии).
2. вы не указали правило упорядочения и определение числа Маркова [я задокументировал себя, также с помощью технических/исследовательских работ, но ничего не нашел (даже правильного определения числа Маркова!!)]

Итак, до тех пор, пока вы не улучшите вопрос таким образом, чтобы он был доступен всем, я буду считать его близким.

Предложения

• спросите сообщество math stackexchange о том, как сгенерировать упорядоченную последовательность Маркова
• перед реализацией yield / yield from у вас должен быть рабочий пример и понимание его(?), т. е. в этом случае выберите другую (более легкую) проблему для начала!
• предоставьте более подробную информацию о проблеме

Рассмотрение

• Числа Маркова являются узлами двоичного дерева, поэтому реализуйте двоичное дерево
• каждый уровень дерева имеет два (относительных) минимальных, наиболее внешних листа, которые описываются последовательностью Фибоначчи и Пелла. Фибоначчи-самый маленький из них. Они могут быть использованы в качестве условия прерывания для размера списка, содержащего n-марковские числа
• чтобы было проще, используйте жадный алгоритм… если вам нужен список n-упорядоченных чисел Маркова, например, рассмотрите идеальное двоичное дерево (оно дорого в вычислительном отношении, размер моделируется геометрическим рядом с начальным значением 1 и общим соотношением 2) и отсортируйте их по возрастанию и рассмотрите 1-е n-записи такого списка, например

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

Опасность как упоминалось в комментарии, в статье википедии узлы, соответствующие номеру Маркова 194, помечены неправильно, см. Мой комментарий для справки. Здесь более подробное марковское дерево, чем в Википедии.

Пример кода, касающегося вычисления листа дерева. Я использую в качестве ссылки идеальное дерево, узлы которого могут быть однозначно описаны в терминах геометрической последовательности, чтобы найти лист, затем найти последовательность левого и правого пути, которые ведут к корню, и, наконец, применить «правила Маркова», чтобы найти тройки:

 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))
 

Выход

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

Обновить. Я смог найти разумно лучшее решение, используя очередь (хотя и не идеальное).

 # 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])
 

Я проверил это до n=39 (начиная с индекса 0). Это совпадает с первыми 40 элементами в 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
 

Это не идеально, потому что все равно необходимо искать намного дальше, чем n, чтобы получить точный результат примерно для n>10. Вот почему существует термин n**3. Если бы кто-нибудь мог объяснить лучший метод, я был бы признателен.