stau.space
My omnium-gatherom of scripts and source code.
1from math import gcd
2import cython
3
4def F(a: cython.int, b: cython.int) -> list[cython.int]:
5 sequence: list[cython.int] = [a, b]
6 while sequence[-1] > 1:
7 sequence.append(-sequence[-2] % sequence[-1])
8
9 return sequence
10
11def search(upper_bound: cython.int, ctn_degree: cython.int) -> set[cython.int]:
12 ctn: set[tuple] = set()
13 for a in range(1, upper_bound + 1, 2):
14 for b in range(1, min(upper_bound, a) + 1, 2):
15 if gcd(a, b) != 1:
16 continue
17 l: list[cython.int] = F(2 * a, b)
18 r: list[cython.int] = F(2 * b, a)
19 head: list[cython.int] = [a, b]
20 read: list[cython.int] = [b, a]
21 l_body: list[cython.int] = l[2:]
22 r_body: list[cython.int] = r[2:][::-1]
23 llen: cython.size_t = len(l_body)
24 rlen: cython.size_t = len(r_body)
25 # insert at 2 if possible
26 if l[-2] == 2 and llen - 1 + rlen == ctn_degree:
27 body: list[cython.int] = l_body[:-1] + r_body[2:]
28 fw: list[cython.int] = head + body
29 bw: list[cython.int] = read + body[::-1]
30 ctn.add(tuple(fw))
31 ctn.add(tuple(bw))
32
33 # insert without one 1 if possible
34 if llen + rlen + 1 == ctn_degree:
35 body: list[cython.int] = l_body[:-1] + r_body
36 fw: list[cython.int] = head + body
37 bw: list[cython.int] = read + body[::-1]
38 ctn.add(tuple(fw))
39 ctn.add(tuple(bw))
40
41 # insert with both ones if possible
42 if llen + rlen + 2 == ctn_degree:
43 body: list[cython.int] = l_body + r_body
44 fw: list[cython.int] = head + body
45 bw: list[cython.int] = read + body[::-1]
46 ctn.add(tuple(fw))
47 ctn.add(tuple(bw))
48
49 elif llen + rlen + 2 < ctn_degree:
50 # add ones if possible
51 ones: cython.size_t = ctn_degree - (len(l_body) + len(r_body) + 2)
52 body: list[cython.int] = l_body + ([1] * ones) + r_body
53 fw: list[cython.int] = head + body
54 bw: list[cython.int] = read + body[::-1]
55 ctn.add(tuple(fw))
56 ctn.add(tuple(bw))
57 return ctn