Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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). –  Joseph O'Rourke May 16 '11 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.