Ducci sequence
A Ducci sequence is a sequence of n-tuples of integers, sometimes known as "the Diffy game", because it is based on sequences.
Given an n-tuple of integers , the next n-tuple in the sequence is formed by taking the absolute differences of neighbouring 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 (1864 - 1940), the Italian mathematician who discovered in the 1930s that every such sequence eventually becomes periodic.
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] [2]
Properties
[edit]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 minimum 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] [3] [4]
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 of form , is a constant, and .
An obvious generalisation of Ducci sequences is to allow the members of the n-tuples to be any real numbers rather than just integers. For example, [2] this 4-tuple converges to (0, 0, 0, 0) in four iterations:
The properties presented here do not always hold for these generalisations. For example, a Ducci sequence starting with the n-tuple (1, q, q2, q3) where q is the (irrational) positive root of the cubic does not reach (0,0,0,0) in a finite number of steps, although in the limit it converges to (0,0,0,0).[5]
Examples
[edit]Ducci sequences may be arbitrarily long before they reach a tuple of zeros or a periodic loop. The 4-tuple sequence starting with (0, 653, 1854, 4063) 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:
If some conditions are imposed on any "power of two"-tuple Ducci sequence, it would take that power of two or lesser iterations to reach the zeros tuple. It is hypothesized that these sequences conform to a rule.[6]
Modulo two form
[edit]When the Ducci sequences enter binary loops, it is possible to treat the sequence in modulo two. That is:[7]
This forms the basis for proving when the sequence vanish to all zeros.
Cellular automata
[edit]![](http://upload.wikimedia.org/wikipedia/commons/1/1f/CA_rule_102.png)
The linear map in modulo 2 can further be identified as the cellular automata denoted as rule 102 in Wolfram code and related to rule 90 through the Martin-Odlyzko-Wolfram map.[8][9] Rule 102 reproduces the Sierpinski triangle.[10]
Other related topics
[edit]The Ducci map is an example of a difference equation, a category that also include non-linear dynamics, chaos theory and numerical analysis. Similarities to cyclotomic polynomials have also been pointed out.[11] While there are no practical applications of the Ducci map at present, its connection to the highly applied field of difference equations led [5] to conjecture that a form of the Ducci map may also find application in the future.
References
[edit]- ^ a b Chamberland, Marc; Thomas, Diana M. (2004). "The N-Number Ducci Game" (PDF). Journal of Difference Equations and Applications. 10 (3): 33–36. doi:10.1080/10236190410001647807. Retrieved 2009-01-26.
- ^ a b Clausing, Achim (2018). "Ducci matrices". American Mathematical Monthly. 125 (10): 901–921. doi:10.1080/00029890.2018.1523661.
- ^ Chamberland, Marc (2003). "Unbounded Ducci sequences" (PDF). Journal of Difference Equations and Applications. 9 (10): 887–895. CiteSeerX 10.1.1.63.6652. doi:10.1080/1023619021000041424. Retrieved 2009-01-26.
- ^ Andriychenko, Oleksiy; Chamberland, Marc (2000). "Iterated Strings and Cellular Automata". The Mathematical Intelligencer. 22 (4): 33–36. doi:10.1007/BF03026764.
- ^ a b Brockman, Greg (2007). "Asymptotic behaviour of certain Ducci sequences" (PDF). Fibonacci Quarterly.
- ^ Euich, Miztani; Akihiro, Nozaki.; Toru, Sawatari. (2013). "A Conjecture of Ducci Sequences and the Aspects" (PDF). RIMS Kokyuroku. 1873: 88–97. Retrieved 2014-02-18.
- ^ Florian Breuer, "Ducci sequences in higher dimensions" in INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007) [1]
- ^ S Lettieri, JG Stevens, DM Thomas, "Characteristic and minimal polynomials of linear cellular automata" in Rocky Mountain J. Math, 2006.
- ^ M Misiurewicz, JG Stevens, DM Thomas, "Iterations of linear maps over finite fields", Linear Algebra and Its Applications, 2006
- ^ Weisstein, Eric W. "Rule 102." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rule102.html
- ^ F. Breuer et al. 'Ducci-sequences and cyclotomic polynomials' in Finite Fields and Their Applications 13 (2007) 293–304
External links
[edit]- Ducci Sequence Archived 2004-08-26 at the Wayback Machine
- Integer Iterations on a Circle at Cut-the-Knot