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?
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.