Ducci sequence

From Wikipedia, the free encyclopedia

A Ducci sequence is a sequence of n-tuples of integers. Given an $n$ -tuple of integers $(a 1, a 2,..., a n),$ a new $n$ -tuple is formed by taking the absolute differences: $( | a 1 - a 2 | , | a 2 - a 3 | ,..., | a n - a 1 | ).$ Put another way: Arrange $n$ numbers on a circle and make a new circle by taking the difference between them. Repeat.

It has been proven that one will reach the sequence (0,0,...,0) in a finite number of steps if and only if $n$ is a power of 2.

With $n$ being a finite number, the sequence must of course start repeating itself sooner or later. It has been proven that for $n$ not a power of two, the Ducci sequence will settle on a loop with 'binary' sequences. That is, with elements composed of only two different digits.

[edit] Example sequence

This 5-tuple sequence enters a period 15 binary 'loop' after 7 iterations.

$\begin{matrix} 1 5 7 9 9\\ 4 2 2 0 8\\ 2 0 2 8 4\\ 2 2 6 4 2\\ 0 4 2 2 0\\ 4 2 0 2 0\\ 2 2 2 2 4\\ \end{matrix}$

$\begin{matrix} 0 0 0 2 2\\ 0 0 2 0 2\\ 0 2 2 2 2\\ 2 0 0 0 2\\ 2 0 0 2 0\\ 2 0 2 2 2\\ 2 2 0 0 0\\ 0 2 0 0 2\\ 2 2 0 2 2\\ 0 2 2 0 0\\ 2 0 2 0 0\\ 2 2 2 0 2\\ 0 0 2 2 0\\ 0 2 0 2 0\\ 2 2 2 2 0\\ \end{matrix}$

$\begin{matrix} 0 0 0 2 2\\ 0 0 2 0 2\\ \end{matrix}$