The sequence is defined as follows:
$$a(1) = 1$$ $$a(2) = k$$
$$a(n + 1) = \frac{a(n) + a(n - 1)}{2^{v}}$$ Basically, you add the last two numbers and divide it by $2$ until it's an odd number.
For example, when $k = 11$, you start with
$$(1, 11)$$
$11 + 1 = 12$, now you divide $12$ by $2$ until it's an odd number, $\frac{12}{2} = 6, \frac{6}{2} = 3$, so the next term is $3$.
$$(1, 11, 3)$$
$3 + 11 = 14$,$\frac{14}{2} = 7$
$$(1, 11, 3, 7)$$
$7 + 3 = 10$, $\frac{10}{2} = 5$
$$(1, 11, 3, 7, 5)$$
$5 + 7 = 12$ $\frac{12}{2} = 6$, $\frac{6}{2} = 3$
$$(1, 11, 3, 7, 5, 3)$$
$3 + 5 = 8$, $\frac{8}{2} = 4$, $\frac{4}{2} = 2$, $\frac{2}{2} = 1$
$$(1, 11, 3, 7, 5, 3, 1)$$
$1 + 3 = 4$, $\frac{4}{2} = 2$, $\frac{2}{2} = 1$
$$(1, 11, 3, 7, 5, 3, 1, 1)$$ once you reach $(1, 1)$ the next terms will all be just 1's, if you try other values of $k$ the same happens, here's a table of the first few:
1: (1, 1, ...)
2: (1, 2, 3, 5, 1, 3, 1, 1, ...)
3: (1, 3, 1, 1, ...)
4: (1, 4, 5, 9, 7, 1, 1, ...)
5: (1, 5, 3, 1, 1, ...)
6: (1, 6, 7, 13, 5, 9, 7, 1, 1, ...)
7: (1, 7, 1, 1, ...)
8: (1, 8, 9, 17, 13, 15, 7, 11, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
9: (1, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
10: (1, 10, 11, 21, 1, 11, 3, 7, 5, 3, 1, 1, ...)
11: (1, 11, 3, 7, 5, 3, 1, 1, ...)
12: (1, 12, 13, 25, 19, 11, 15, 13, 7, 5, 3, 1, 1, ...)
13: (1, 13, 7, 5, 3, 1, 1, ...)
14: (1, 14, 15, 29, 11, 5, 1, 3, 1, 1, ...)
15: (1, 15, 1, 1, ...)
16: (1, 16, 17, 33, 25, 29, 27, 7, 17, 3, 5, 1, 3, 1, 1, ...)
17: (1, 17, 9, 13, 11, 3, 7, 5, 3, 1, 1, ...)
18: (1, 18, 19, 37, 7, 11, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
19: (1, 19, 5, 3, 1, 1, ...)
20: (1, 20, 21, 41, 31, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
21: (1, 21, 11, 1, 3, 1, 1, ...)
22: (1, 22, 23, 45, 17, 31, 3, 17, 5, 11, 1, 3, 1, 1, ...)
23: (1, 23, 3, 13, 1, 7, 1, 1, ...)
24: (1, 24, 25, 49, 37, 43, 5, 3, 1, 1, ...)
25: (1, 25, 13, 19, 1, 5, 3, 1, 1, ...)
26: (1, 26, 27, 53, 5, 29, 17, 23, 5, 7, 3, 5, 1, 3, 1, 1, ...)
27: (1, 27, 7, 17, 3, 5, 1, 3, 1, 1, ...)
28: (1, 28, 29, 57, 43, 25, 17, 21, 19, 5, 3, 1, 1, ...)
29: (1, 29, 15, 11, 13, 3, 1, 1, ...)
30: (1, 30, 31, 61, 23, 21, 11, 1, 3, 1, 1, ...)
31: (1, 31, 1, 1, ...)
32: (1, 32, 33, 65, 49, 57, 53, 55, 27, 41, 17, 29, 23, 13, 9, 11, 5, 1, 3, 1, 1, ...)
33: (1, 33, 17, 25, 21, 23, 11, 17, 7, 3, 5, 1, 3, 1, 1, ...)
34: (1, 34, 35, 69, 13, 41, 27, 17, 11, 7, 9, 1, 5, 3, 1, 1, ...)
35: (1, 35, 9, 11, 5, 1, 3, 1, 1, ...)
36: (1, 36, 37, 73, 55, 1, 7, 1, 1, ...)
37: (1, 37, 19, 7, 13, 5, 9, 7, 1, 1, ...)
38: (1, 38, 39, 77, 29, 53, 41, 47, 11, 29, 5, 17, 11, 7, 9, 1, 5, 3, 1, 1, ...)
39: (1, 39, 5, 11, 1, 3, 1, 1, ...)
40: (1, 40, 41, 81, 61, 71, 33, 13, 23, 9, 1, 5, 3, 1, 1, ...)
41: (1, 41, 21, 31, 13, 11, 3, 7, 5, 3, 1, 1, ...)
42: (1, 42, 43, 85, 1, 43, 11, 27, 19, 23, 21, 11, 1, 3, 1, 1, ...)
43: (1, 43, 11, 27, 19, 23, 21, 11, 1, 3, 1, 1, ...)
44: (1, 44, 45, 89, 67, 39, 53, 23, 19, 21, 5, 13, 9, 11, 5, 1, 3, 1, 1, ...)
45: (1, 45, 23, 17, 5, 11, 1, 3, 1, 1, ...)
46: (1, 46, 47, 93, 35, 1, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
47: (1, 47, 3, 25, 7, 1, 1, ...)
48: (1, 48, 49, 97, 73, 85, 79, 41, 15, 7, 11, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
49: (1, 49, 25, 37, 31, 17, 3, 5, 1, 3, 1, 1, ...)
50: (1, 50, 51, 101, 19, 15, 17, 1, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
51: (1, 51, 13, 1, 7, 1, 1, ...)
52: (1, 52, 53, 105, 79, 23, 51, 37, 11, 3, 7, 5, 3, 1, 1, ...)
53: (1, 53, 27, 5, 1, 3, 1, 1, ...)
54: (1, 54, 55, 109, 41, 75, 29, 13, 21, 17, 19, 9, 7, 1, 1, ...)
55: (1, 55, 7, 31, 19, 25, 11, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
56: (1, 56, 57, 113, 85, 99, 23, 61, 21, 41, 31, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
57: (1, 57, 29, 43, 9, 13, 11, 3, 7, 5, 3, 1, 1, ...)
58: (1, 58, 59, 117, 11, 1, 3, 1, 1, ...)
59: (1, 59, 15, 37, 13, 25, 19, 11, 15, 13, 7, 5, 3, 1, 1, ...)
60: (1, 60, 61, 121, 91, 53, 9, 31, 5, 9, 7, 1, 1, ...)
61: (1, 61, 31, 23, 27, 25, 13, 19, 1, 5, 3, 1, 1, ...)
62: (1, 62, 63, 125, 47, 43, 45, 11, 7, 9, 1, 5, 3, 1, 1, ...)
63: (1, 63, 1, 1, ...)
64: (1, 64, 65, 129, 97, 113, 105, 109, 107, 27, 67, 47, 57, 13, 35, 3, 19, 11, 15, 13, 7, 5, 3, 1, 1, ...)
65: (1, 65, 33, 49, 41, 45, 43, 11, 27, 19, 23, 21, 11, 1, 3, 1, 1, ...)
66: (1, 66, 67, 133, 25, 79, 13, 23, 9, 1, 5, 3, 1, 1, ...)
67: (1, 67, 17, 21, 19, 5, 3, 1, 1, ...)
68: (1, 68, 69, 137, 103, 15, 59, 37, 3, 5, 1, 3, 1, 1, ...)
69: (1, 69, 35, 13, 3, 1, 1, ...)
70: (1, 70, 71, 141, 53, 97, 75, 43, 59, 51, 55, 53, 27, 5, 1, 3, 1, 1, ...)
71: (1, 71, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
72: (1, 72, 73, 145, 109, 127, 59, 93, 19, 7, 13, 5, 9, 7, 1, 1, ...)
73: (1, 73, 37, 55, 23, 39, 31, 35, 33, 17, 25, 21, 23, 11, 17, 7, 3, 5, 1, 3, 1, 1, ...)
74: (1, 74, 75, 149, 7, 39, 23, 31, 27, 29, 7, 9, 1, 5, 3, 1, 1, ...)
75: (1, 75, 19, 47, 33, 5, 19, 3, 11, 7, 9, 1, 5, 3, 1, 1, ...)
76: (1, 76, 77, 153, 115, 67, 91, 79, 85, 41, 63, 13, 19, 1, 5, 3, 1, 1, ...)
77: (1, 77, 39, 29, 17, 23, 5, 7, 3, 5, 1, 3, 1, 1, ...)
78: (1, 78, 79, 157, 59, 27, 43, 35, 39, 37, 19, 7, 13, 5, 9, 7, 1, 1, ...)
79: (1, 79, 5, 21, 13, 17, 15, 1, 1, ...)
80: (1, 80, 81, 161, 121, 141, 131, 17, 37, 27, 1, 7, 1, 1, ...)
81: (1, 81, 41, 61, 51, 7, 29, 9, 19, 7, 13, 5, 9, 7, 1, 1, ...)
82: (1, 82, 83, 165, 31, 49, 5, 27, 1, 7, 1, 1, ...)
83: (1, 83, 21, 13, 17, 15, 1, 1, ...)
84: (1, 84, 85, 169, 127, 37, 41, 39, 5, 11, 1, 3, 1, 1, ...)
85: (1, 85, 43, 1, 11, 3, 7, 5, 3, 1, 1, ...)
86: (1, 86, 87, 173, 65, 119, 23, 71, 47, 59, 53, 7, 15, 11, 13, 3, 1, 1, ...)
87: (1, 87, 11, 49, 15, 1, 1, ...)
88: (1, 88, 89, 177, 133, 155, 9, 41, 25, 33, 29, 31, 15, 23, 19, 21, 5, 13, 9, 11, 5, 1, 3, 1, 1, ...)
89: (1, 89, 45, 67, 7, 37, 11, 3, 7, 5, 3, 1, 1, ...)
90: (1, 90, 91, 181, 17, 99, 29, 1, 15, 1, 1, ...)
91: (1, 91, 23, 57, 5, 31, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
92: (1, 92, 93, 185, 139, 81, 55, 17, 9, 13, 11, 3, 7, 5, 3, 1, 1, ...)
93: (1, 93, 47, 35, 41, 19, 15, 17, 1, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
94: (1, 94, 95, 189, 71, 65, 17, 41, 29, 35, 1, 9, 5, 7, 3, 5, 1, 3, 1, 1, ...)
95: (1, 95, 3, 49, 13, 31, 11, 21, 1, 11, 3, 7, 5, 3, 1, 1, ...)
96: (1, 96, 97, 193, 145, 169, 157, 163, 5, 21, 13, 17, 15, 1, 1, ...)
97: (1, 97, 49, 73, 61, 67, 1, 17, 9, 13, 11, 3, 7, 5, 3, 1, 1, ...)
98: (1, 98, 99, 197, 37, 117, 77, 97, 87, 23, 55, 39, 47, 43, 45, 11, 7, 9, 1, 5, 3, 1, 1, ...)
99: (1, 99, 25, 31, 7, 19, 13, 1, 7, 1, 1, ...)
def a(k):
sequence = [1, k]
while sequence[-2:] != [1, 1]:
next_term = sequence[-1] + sequence[-2]
while next_term % 2 == 0:
next_term //= 2
sequence.append(next_term)
return sequence[:-2]
If you graph the number of terms $k$ needs before reaching $(1, 1)$ it looks pretty random:
Does the sequence reach $(1, 1)$ for every positive integer value of $k$?
Yes. To show this, I will consider the sequences $M(n) = \max(a(n), a(n+1))$ and $G(n) = \gcd(a(n), a(n+1))$.
First, let's consider $M$. To do this, we need to first note that $a(n)$ is odd for $n \geq 3$, which will be used repeatedly, so until we're done talking about $M$ and its relationship to $a$, I will always be assuming $n \geq 3$.
Since $a(n)$ and $a(n+1)$ are odd, their sum is even, so in particular $a(n+2) \leq \frac{a(n)+a(n+1)}2 \leq M(n)$. By definition, $a(n+1) \leq M(n)$, so it follows that $M(n+1) \leq M(n)$. As $M$ is a weakly decreasing sequence of positive integers [for $n\geq 3$], it must eventually stabilize.
Let $n_0$ denote a value of $n$ such that $M(n_0) = M(n_0+1) = M(n_0+2)=\ldots$, and suppose $a(n_0) \neq a(n_0+1)$. If $a(n_0) > a(n_0+1)$, then $$a(n_0+2) \leq \frac{a(n_0)+a(n_0+1)}2 < a(n_0) = M(n_0),$$ but then $M(n_0+1) < M(n_0)$, a contradiction. On the other hand, if $a(n_0) < a(n_0+1)$, then $a(n_0+2) < a(n_0+1)$ and by the previous case's argument $M(n_0+2) < M(n_0+1)$, again a contradiction. It follows that $a(n_0) = a(n_0+1)$, at which point it is easy to show by induction that $a(n) = a(n_0)$ for every $n \geq n_0$.
That is, we have shown $a(n)$ eventually stabilizes.
Now consider $G$. Here, we just note that $G(n+1) \mid a(n+1)$ and $$G(n+1) = \gcd(a(n+1),a(n+2)) \mid 2^va(n+2) - a(n+1) = a(n),$$ so $G(n+1) \mid \gcd(a(n),a(n+1)) = G(n)$. By induction, $$a(n_0) = G(n_0) \mid G(1) = \gcd(1,k) = 1,$$ so that $a(n_0) = 1$.
This finishes the proof.
Going back through the proof, we actually see that we proved something slightly stronger:
Also, we can extract an upper bound on the smallest such $n_0$, but it's unlikely to be of interest outside of this proof: $$n_0 \leq 2M(3)+2 \leq 2(a(3)+a(4))+2 \leq 6(k+1)$$