9
$\begingroup$

Given an arbitrary sequence of nonnegative integers $x_0, \ldots, x_{n-1}$, define its difference sequence as x'_i = | x_i - x_{i+1} |, with indices mod $n$ (so $x_n = x_0$). Repeated application of this process leads to interesting behavior. For example, for $n=2^k$, it appears the process always ends with the zero sequence:

 181,530,245,548,294,228,364,958 349,285,303,254,66,136,594,777 64,18,49,188,70,458,183,428 46,31,139,118,388,275,245,364 15,108,21,270,113,30,119,318 93,87,249,157,83,89,199,303 6,162,92,74,6,110,104,210 156,70,18,68,104,6,106,204 86,52,50,36,98,100,98,48 34,2,14,62,2,2,50,38 32,12,48,60,0,48,12,4 20,36,12,60,48,36,8,28 16,24,48,12,12,28,20,8 8,24,36,0,16,8,12,8 16,12,36,16,8,4,4,0 4,24,20,8,4,0,4,16 20,4,12,4,4,4,12,12 16,8,8,0,0,8,0,8 8,0,8,0,8,8,8,8 8,8,8,8,0,0,0,0 0,0,0,8,0,0,0,8 0,0,8,8,0,0,8,8 0,8,0,8,0,8,0,8 8,8,8,8,8,8,8,8 0,0,0,0,0,0,0,0 

Is this a theorem? For $n$ not a power of 2, it falls into cycles where all elements are 0 or $m$ for some integer $m$ (usually $m=1$).

Have these difference sequences been studied? They seem to have a rich structure.

1 Answers 1

9

They're called Ducci sequences. The proof that they terminate for $n = 2^k$ is fairly elementary: all you have to show is that eventually all of the terms are even, and then you're done by induction on the binary expansion. To show that eventually all of the terms are even it suffices to work $\bmod 2$, and then you're just looking at powers of the matrix $I + P$ over $\mathbb{F}_2$, where $P$ is a cyclic permutation. We have $(I + P)^{2^k} \equiv I + P^{2^k} \bmod 2$, so when $n = 2^k$ we are guaranteed that after at most $n$ steps all of the terms are even (and otherwise we get the behavior you already described).

  • 0
    Thanks for this knowledgeable answer! I would just like to point out that having all terms even does not suffice to lead to zeros; rather it does only when $n$ is a power of 2 (which is I know exactly what you meant).2011-05-16