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}),$ 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. Ignore any minus signs and repeat the operation. Ducci sequences are named for Enrico Ducci, the Italian mathematician credited with their discovery.

It has been proven that one will always reach the sequence (0,0,...,0) in a finite number of steps 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 proved that if $n$ is not a power of two, the Ducci sequence will either converge to zeros or settle on a loop with 'binary' sequences. That is, with elements composed of only two different digits.

Example sequences

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

${\begin{matrix}15799\\42208\\20284\\22642\\04220\\42020\\22224\\\end{matrix}}$

${\begin{matrix}00022\\00202\\02222\\20002\\20020\\20222\\22000\\02002\\22022\\02200\\20200\\22202\\00220\\02020\\22220\\\end{matrix}}$

${\begin{matrix}00022\\00202\\\end{matrix}}$

The following sequence has length 6 which is not a power of two, but it still converges to zeros:

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

Ducci sequences are also known as the n-numbers game. Numerous extensions and generalisations exist.

External links

• Ducci Sequence
• Integer Iterations on a Circle