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.^[1]

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, the sequence of n-tuples must sooner or later repeat itself. Every Ducci sequence therefore eventually becomes 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.^[1] ^[2] ^[3]

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

Ducci sequences may be arbitrarily long before they reach a tuple of zeros or a periodic loop. The following 4-tuple sequence takes 24 iterations to reach the zeros tuple.

${\begin{matrix}(0,653,1854,4063)&(653,1201,2209,4063)&(548,1008,1854,3410)&(460,846,1556,2862)\\(386,710,1306,2402)&(324,596,1096,2016)&(272,500,920,1692)&(228,420,772,1420)\\(192,352,648,1192)&(160,296,544,1000)&(136,248,456,840)&(112,208,384,704)\\(96,176,320,592)&(80,144,272,496)&(64,128,224,416)&(64,96,192,352)\\(32,96,160,288)&(64,64,128,256)&(0,64,128,192)&(64,64,64,192)\\(0,0,128,128)&(0,128,0,128)&(128,128,128,128)&(0,0,0,0)\\\end{matrix}}$

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}}$

References

^ ^a ^b Chamberland, Marc; Thomas, Diana M. (2004). "The N-Number Ducci Game" (PDF). Journal of Difference Equations and Applications. 10 (3). London: Taylor & Francis: 33–36. Retrieved 2009-01-26.
^ Chamberland, Marc (2003). "Unbounded Ducci sequences" (PDF). Journal of Difference Equations and Applications. 9 (10). London: Taylor & Francis: 887–895. Retrieved 2009-01-26.
^ Andriychenko, O.; Chamberland, Marc (2000). "Iterated Strings and Cellular Automata". The Mathematical Intelligencer. 22 (4). New York, NY: Springer Verlag: 33–36.

External links

This number theory-related article is a stub. You can help Wikipedia by expanding it.

[Chamberland&Thomas2004-1] Chamberland, Marc; Thomas, Diana M. (2004). "The N-Number Ducci Game" (PDF). Journal of Difference Equations and Applications. 10 (3). London: Taylor & Francis: 33–36. Retrieved 2009-01-26.

[Chamberland2003-2] Chamberland, Marc (2003). "Unbounded Ducci sequences" (PDF). Journal of Difference Equations and Applications. 9 (10). London: Taylor & Francis: 887–895. Retrieved 2009-01-26.

[Andriychenko&Chamberland2000-3] Andriychenko, O.; Chamberland, Marc (2000). "Iterated Strings and Cellular Automata". The Mathematical Intelligencer. 22 (4). New York, NY: Springer Verlag: 33–36.

[1]

[2]

[3]