Does this sequence always go to $(0,0,0,0)$?

176 Views Asked by At

Start with a sequence $S =(a, b, c, d)$ of positive integers and find the derived sequence $$S_1 = T(S) = (|a −b|, |b−c|, |c−d|, |d −a|).$$

Does the sequence $S, S_1, S_2 = T(S_1), S_3 = T(S_2), \ldots$ always end up with $(0, 0, 0, 0)$?

Observations:

$(0, 3, 10, 13) \rightarrow (3, 7, 3, 13) → (4, 4, 10, 10) →(0, 6, 0, 6) → (6, 6, 6, 6) → (0, 0, 0, 0)$

$(8, 17, 3, 107) → (9, 14, 104, 99) → (5, 90, 5, 90) → (85, 85, 85, 85) → (0, 0, 0, 0)$

$(91, 108, 95, 294) → (17, 13, 99, 203) → (4, 86, 104, 186) → (82, 18, 82, 182) → (64, 64, 100, 100) → (0, 36, 0, 36) → (36, 36, 36, 36) → (0, 0, 0, 0)$

2

There are 2 best solutions below

0
On BEST ANSWER

(This is Ross Millikan's answer, but in more detail.)

Consider your recursion scheme mod $2$. Then $$(0,1,0,0),\ (1,0,1,1)\to(1,1,0,0)\to(0,1,0,1)\to(1,1,1,1)\to(0,0,0,0)\to(0,0,0,0).$$ Since (modulo rotation) each of the $16$ possible bitstrings of length $4$ occurs in this sequence, and all of them are transformed into $(0,0,0,0)$ after at most $4$ steps we know that after $\leq4$ steps the resulting quadruple consists of even numbers only. At this point we can divide all four numbers by $2$ without harm done concerning the length of the procedure. After at most $4$ further steps we again have arrived at an even quadruple and can again divide by $2$, and so on. Noting that the $\max$ of the $a_i$ can only decrease in one step it follows that all is over after about $4\lceil\log_2(m)\rceil$ steps, where $m$ is the largest of the numbers $a_i$ given at the beginning.

2
On

Yes, it does. To show it, consider the binary expansion of the numbers. You have $(1,0,0,0)\to (1,1,0,0) \to (1,0,1,0) \to (1,1,1,1) \to (0,0,0,0)$. Considering that rotation and complement don't change things, after at most four operations all the numbers will be even. As you say, the maximum number cannot increase. Four more tries and all the numbers will be multiples of $4$. If $m$ is the maximum starting number, you will get to $(0,0,0,0)$ within $ 4 \lceil \log_2 m\rceil$ operations