15
$\begingroup$

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:

desmos graph

Does the sequence reach $(1, 1)$ for every positive integer value of $k$?

$\endgroup$
1
  • 7
    $\begingroup$ Some pointers on notation: If you use brackets to denote arrays, make it explicit what your notation means (that is, announce any uncommon notation before use). Unless the mutability of an array is crucial (e.g. when analyzing the runtime of an algorithm), it's better to use tuples in the mathematical notation instead. Also note that the notation $a(i,j)$ implies that we're talking about a sequence dependent on two indices, correct would have been $(a(1),a(2))=(1,k)$, though since we don't need the tuple anywhere, even better would be to simplify the notation to two lines $a(1)= 1, a(2)=k$ $\endgroup$
    – Sudix
    Commented Jul 18, 2023 at 4:53

1 Answer 1

16
$\begingroup$

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:

No matter the choice of the positive integers $a(1),a(2)$, there will be some $n_0$ such that $a(n) = a(n_0)$ for every $n\geq n_0$ and $a(n_0) \mid \gcd(a(1),a(2))$. As an immediate corollary, if $a(1),a(2)$ are relatively prime, then there is some $n_0$ such that $a(n) = 1$ for all $n \geq n_0$.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .