Ducci sequences

Pick four integers a, b, c, and d. Now iterate the procedure that takes these four integers to

|b - a|, |c - b|, |d - c|, |a - d|

You could think of the four integers being arranged clockwise in a circle, taking the absolute value of difference between each number and its neighbor a quarter turn clockwise. The sequence of 4-tuples created this way is called a Ducci sequence.

We can play with Ducci sequences using the following Python code.

 def next(x): n = len(x) return [abs(x[i] - x[(i+1)%n]) for i in range(n)]

If we start with four numbers taken from today's date, the sequence will terminate in zeros in five steps. The code

 x = [7, 10, 20, 22] for _ in range(5): x = next(x) print(x)

This produces

 [3, 10, 2, 15] [7, 8, 13, 12] [1, 5, 1, 5] [4, 4, 4, 4] [0, 0, 0, 0]

The sequence always terminates for any starting point, and usually it terminates quickly, as in the example below. However, you can find starting values so that the sequence takes arbitrarily long to terminate.

In fact, the worse case for termination comes from consecutive Tribonacci numbers [1]. These numbers are defined analogously to Fibonacci numbers, but starting with 0, 0, 1, and each subsequent number being the sum of the previous 3 numbers.

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, ...

If you start with T_n, T_n+1, T_n+2, T_n+3 then the corresponding Ducci sequence takes at least 3n/2 steps to converge to 0.

Note that the code above does not assume we use sequences of 4 numbers. If we use n-tuples where n is a power of 2, the Ducci sequence always terminates in zeros. More generally the sequence will terminate in a cycle.

For example, suppose we start with 7, 10, and 22. Then the sequence of iterations is

 [3, 12, 15] [9, 3, 12] [6, 9, 3] [3, 6, 3] [3, 3, 0] [0, 3, 3] [3, 0, 3] [3, 3, 0] ...

***

[1] Achim Clausing, Ducci Matrices. American Mathematical Monthly, December 2018.

The post Ducci sequences first appeared on John D. Cook.