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.

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 proven 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