Ducci sequence
A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers , the next n-tuple in the sequence is formed by taking the absolute differences of neigbouring integers:
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 Ducci map or the n-number game. Open problems in the study of these maps still remain.[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.
Numerous generalisations of ducci-sequences have been constructed, for instance replacing the integers with vectors or changing the rules for mapping to the next iteration. The properties presented here do not always hold for these generalisations.[4]
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.
This 5-tuple sequence enters a period 15 binary 'loop' after 7 iterations.
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:
Related topics
The ducci map is regarded as a playful topic and deceptively simple [4] which has helped it garner interest from researchers, though there has not yet been any practical use for it[4]. But it also falls under the topic of difference equations, a field with many practical applications. As such, ducci sequences share a neighbourhood with topics such as non-linear dynamics, chaos theory and numerical analysis. It is therefore altogether possible that a practical use of ducci sequences may one day appear[4].
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, Oleksiy; Chamberland, Marc (2000). "Iterated Strings and Cellular Automata". The Mathematical Intelligencer. 22 (4). New York, NY: Springer Verlag: 33–36.
- ^ a b c d Brockman, Greg (2007). "Asymptotic behaviour of certain ducci sequences" (PDF). Fibonacci Quarterly.
External links
 | This number theory-related article is a stub. You can help Wikipedia by expanding it. |