3

I am a novice when it comes to mathematics, but I have been give a problem that is causing quite the headache. Basically, I need to know if two values are able to infinitely go against one another given a basic set of rules. The lower number is always multiplied times 2 and the lower number is always subtracted from the higher number, so the sum always stays the same. When either x or y hits 0 the sequence will be terminated, and is therefore finite.

Ex. Where x = 1 and y = 7. Then the next steps would be x = 2 and y = 6, x = 4 and y = 4 x = 8 and y = 0.

I've already concluded that a number is unable to go infinite when x = y, which also means that when the sum of x and y is odd it should always go infinite. But that's about it when it, I've also noticed that when the sum is equal to a power of 2 the combination is also finite.

I've attempted a recursive function where each the combination of numbers will be recorded, and the function will stop when either a pair has been detected that has already occurred in the sequence before (x=2,y=4 will always be alternating between the values therefore detecting a duplicate) indicating the sequence can go infinite, or when x is equal to y indicating that the sequence is finite. The problem here was the number of iterations required to find an awnser.

Apologies if this has been posted before or if the question is a little vague.

Any help of pointers in the right direction would be greatly appreciated.

CaesarSalad
  • 31
  • For a "dual sequence" like that, the first step that makes the problem easier is usually to write is as a single sequence of vectors, $X_n = (x_n; y_n)$, with a simple linear recurrence $X_{n+1} = M X_n$, where $M$ is a 2x2 matrix. Then you get $X_n = M^n X_0$. The second step is to diagonalise $M$, writing $M = P D P^{-1}$, so that $M^n = P D P^{-1} P D P^{-1} ... P D P^{-1} = P D^n P^{-1}$, and $D^n$ is super easy to calculate because $D$ is diagonal. – Stef Aug 19 '22 at 08:02
  • Well, that works easily if x is always the smallest number and y is always the biggest number. That doesn't work if they can switch roles :( – Stef Aug 19 '22 at 08:04
  • I don't think it really matters if the x or y is the highest/lowest number a simple min/max function can be added to determine that x or y will always be highest, do you have an example by any chance? – CaesarSalad Aug 19 '22 at 08:48
  • It does matter if you want to be able to write $X_{n+1} = M X_n$ and $X_n = M^n X_n$. If $x_n$ and $y_n$ swap places every now and then, then there is no matrix $M$ that works; instead, we'd need two matrices $M_1$ and $M_2$, and we sometimes have $X_{n+1} = M_1 X_n$ and sometimes $X_{n+1} = M_2 X_n$, depending on who's larger between $x_n$ and $y_n$. – Stef Aug 19 '22 at 09:23
  • However you can do a reasoning like "Assume without loss of generality that $x_0 > y_0$. Let $n_0$ be the smallest integer such that $y_{n_0} \geq x_{n_0}$, if it exists. Then for all $n < n_0$, we have $X_{n+1} = M X_n$; thus $X_{n_0} = M^{n_0} X_0$." And this gives you an equation on $n_0$. – Stef Aug 19 '22 at 09:25
  • Having one value equal to $0$ does not actually stop the process. You can still do the calculation. it is just that the numbers do not change. But that is not the only way a pair can become unchanging. If the larger number is twice the smaller, the pair also does not change. Do you count this as terminating as well? Or is a $0$ the only termination condition you are interested in? – Paul Sinclair Aug 20 '22 at 14:50

1 Answers1

1

First, note that if some integer $k$ divides both numbers in a pair, it will also divide both numbers after the operation. Also note that the original pair $(x,y)$ will lead to a termination if and only if $\left(\frac xk,\frac yk\right)$ also leads to a termination. So it suffices to figure out what happens when the original $x, y$ are coprime. (In this I am assuming that termination means one of the values becomes $0$.)

The inverse of this fact is almost true as well: if you apply the operation to $(x_0, y_0)$ to get $(x_1, y_1)$, and there is some odd $k$ such that $k \mid x_1$ and $k \mid y_1$, then $k \mid x_0$ and $k \mid y_0$. However, the same is not true for $k = 2$. If $x_0, y_0$ are both odd, then $2 \mid x_1, 2 \mid y_1$.

More generally, if $2^n \mid x_0, 2^n \mid y_0$ and $2^{n+1} \mid (x_0 + y_0)$, then $2^{n+1} \mid x_1, 2^{n+1} \mid y_1$. For labelling the numbers so that $x_0 \le y_0$, we get $x_1 = 2x_0$, so $2^{n+1} \mid x_1$, and if $s = x_0 + y_0$, then $x_1, y_1$ have the same sum, so $y_1 = s - x_1$, and since $2^{n+1}$ divides both $s$ and $x_1$, it divides $y_1$ as well.

This observation leads to the solution to your problem: if $x_0, y_0$ are coprime, then the sequence they induce will terminate if and only if $x_0 + y_0 = 2^n$ for some $n$. If $x_0 + y_0 = 2^n$, then by induction, $2^k$ will divide both $x_k$ and $y_k$ for all $k \le n$. In particular, $2^n \mid x_n$ and $2^n \mid y_n$, but still $x_n + y_n = 2^n$. The only way this can be is if $x_n = 0$ or $y_n = 0$.

Conversely, if $x_0 + y_0 \ne 2^n$ for any $n$, then there is some $n, m$ with $m > 1$ and odd, such that $x_0 + y_0 = 2^nm$. It will still be true that $2^n$ will divide both $x_n$ and $y_n$. However if you define $(s_0, t_0) = \left(\frac{x_n}{2^n}, \frac{y_n}{2^n}\right)$, then $s_0 + t_0 = m$, which is odd. Thus as you've noted, the sequence beginning with $(s_0, t_0)$ can never terminate. But for all $k$, $(x_{n+k}, y_{n+k}) = (2^ns_k, 2^nt_k)$, so that sequence cannot terminate either.

So a coprime pair $(x,y)$ will lead to a non-terminating sequence if and only if $x + y$ is not a power of $2$. More generally, any pair $(x,y)$ will produce a non-terminating sequence if and only if $\frac{x+y}{\gcd(x,y)}$ is not a power of $2$.

Paul Sinclair
  • 43,643
  • So to make it clear to me, the induction step needed in the fourth paragraph goes something like this: $$ 2^k\mid x_k,y_k\text{ and }2^n\mid(x_k+y_k)\implies 2^{k+1}\mid x_{k+1}=2x_k,y_{k+1}=x_k+y_k-2x_k $$ – String Aug 21 '22 at 09:09
  • As was pointed out in the OP, the sum of $x+y$ does not change under the operation. Call that constant sum $s$. The assumption is $2^n\mid s$, and $k+1 \le n$ (this is a finite induction), so $2^{k+1} \mid s$. Also $2^k \mid x_k$, so $2^{k+1} \mid x_{k+1}$. But $x_{k+1} + y_{k+1} = s$. Since $2^{k+1}$ divides both $x_{k+1}$ and $s$, it must also divide $y_{k+1} = s = x^{k+1}$. – Paul Sinclair Aug 21 '22 at 13:59
  • That final equation was supposed to be $y_{k+1} = s - x_{k+1}$. I have discovering typos just too late to correct them. – Paul Sinclair Aug 21 '22 at 14:08