Ducci sequence

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers $(a_{1},a_{2},...,a_{n})$, the next n-tuple in the sequence is formed by taking the absolute differences of neigbouring integers:

$(a_{1},a_{2},...,a_{n})\rightarrow (|a_{1}-a_{2}|,|a_{2}-a_{3}|,...,|a_{n}-a_{1}|)\,.$

Another way of describing this is as follows. Arrange n integers in a circle and make a new circle by taking the difference between neighbours, ignoring any minus signs; then repeat the operation. Ducci sequences are named after Enrico Ducci, the Italian mathematician credited with their discovery.

Ducci sequences are also known as the n-number game.

Properties

From the second n-tuple onwards, it is clear that every integer in each n-tuple in a Ducci sequence is greater than or equal to 0 and is less than or equal to the difference between the maximum and mimimum members of the first n-tuple. As there are only a finite number of possible n-tuples with these constraints, it is clear that every Ducci sequence is eventually periodic.

If n is a power of 2 every Ducci sequence eventually reaches the n-tuple (0,0,...,0) in a finite number of steps.

If n is not a power of two, a Ducci sequence will either eventually reach an n-tuple of zeros or will settle into a periodic loop of 'binary' n-tuples; that is, n-tuples which contain only two different digits.

Examples

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

${\begin{matrix}15799&42208&20284&22642&04220&42020\\22224&00022&00202&02222&20002&20020\\20222&22000&02002&22022&02200&20200\\22202&00220&02020&22220&00022&00202\\\end{matrix}}$

The following 6-tuple sequence shows that sequences of tuples whose length is not a power of two may still reach a tuple of zeros:

${\begin{matrix}121210&111111&000000\\\end{matrix}}$

External links

• Ducci Sequence
• Integer Iterations on a Circle at Cut-the-Knot