imported>Citation bot: Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Sequences and series | #UCB_Category 32/47

2025-06-14T04:46:33Z

Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Sequences and series | #UCB_Category 32/47

New page

{{Short description|Sequence of n-tuples of integers}}
A '''Ducci sequence''' is a [[sequence]] of [[n-tuple|''n''-tuples]] of [[integer]]s, sometimes known as "the Diffy game", since it based on differences (subtractions).

Given an ''n''-tuple of integers <math>(a_1,a_2,...,a_n)</math>, the next ''n''-tuple in the sequence is formed by taking the absolute differences of neighbouring integers:

:<math>(a_1,a_2,...,a_n) \rightarrow (|a_1-a_2|, |a_2-a_3|, ..., |a_n-a_1|)\, .</math>

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.<ref name="Chamberland&Thomas2004">{{cite journal
| last1 = Chamberland
| first1 = Marc
| last2 = Thomas
| first2 = Diana M.
| title = The N-Number Ducci Game
| journal = Journal of Difference Equations and Applications
| volume = 10
| issue = 3
| pages = 33–36
| year = 2004
| url = http://www.math.grinnell.edu/~chamberl/papers/ducci_survey.pdf
| accessdate = 2009-01-26| doi = 10.1080/10236190410001647807
}}</ref>
<ref name="Clausing">{{cite journal
| doi = 10.1080/00029890.2018.1523661
| last = Clausing
| first = Achim
| title = Ducci matrices
| journal = American Mathematical Monthly
| volume = 125
| issue = 10
| pages = 901–921
| year = 2018}}
</ref>

==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 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 function|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.<ref name="Chamberland&Thomas2004" />
<ref name="Chamberland2003">{{cite journal
| doi = 10.1080/1023619021000041424
| last = Chamberland
| first = Marc
| title = Unbounded Ducci sequences
| journal = Journal of Difference Equations and Applications
| volume = 9
| issue = 10
| pages = 887–895
| year = 2003
| url = http://www.math.grinnell.edu/~chamberl/papers/ducci_unbounded.pdf
| accessdate = 2009-01-26| citeseerx = 10.1.1.63.6652
}}</ref>
<ref name="Andriychenko&Chamberland2000">{{cite journal
| last1 = Andriychenko
| first1 = Oleksiy
| last2 = Chamberland
| first2 = Marc
| title = Iterated Strings and Cellular Automata
| journal = [[The Mathematical Intelligencer]]
| volume = 22
| issue = 4
| pages = 33–36
| year = 2000
| doi = 10.1007/BF03026764}}</ref>

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 <math>k(b_1, b_2, ... b_n)</math>, <math>k</math> is a constant, and <math>b_i \in \{0, 1\}</math>.

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,
<ref name="Clausing" /> this 4-tuple converges to (0, 0, 0, 0) in four iterations:
<math>
(e, \pi, \sqrt2, 1) \rightarrow
(\pi - e, \pi - \sqrt2, \sqrt2 - 1, e - 1) \rightarrow
(e - \sqrt2, \pi - 2\sqrt2 + 1, e - \sqrt2, 2e - \pi - 1) \rightarrow
</math>
<math>
(\pi - e - \sqrt2 + 1, \pi - e - \sqrt2 + 1, \pi - e - \sqrt2 + 1, \pi - e - \sqrt2 + 1)
\rightarrow (0, 0, 0, 0)
</math>

The properties presented here do not always hold for these generalisations. For example, a Ducci sequence starting with the ''n''-tuple (1, ''q'', ''q''<sup>2</sup>, ''q''<sup>3</sup>) where ''q'' is the (irrational) positive root of the cubic <math>x^3 - x^2 - x - 1 = 0</math> does not reach (0,0,0,0) in a finite number of steps, although in the limit it converges to (0,0,0,0).<ref name="Brockman">{{cite journal
| last1 = Brockman
| first1 = Greg
| title = Asymptotic behaviour of certain Ducci sequences
| journal = [[Fibonacci Quarterly]]
| url = http://www.cut-the-knot.org/Curriculum/Algebra/GregBrockman/GregBrockmanDucciSequencesPaper.pdf
| year = 2007| volume = 45
| issue = 2
| pages = 155–163
| doi = 10.1080/00150517.2007.12428232
}}
</ref>

==Examples==
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.

<math>
(0, 653, 1854, 4063) \rightarrow
(653, 1201, 2209, 4063) \rightarrow
(548, 1008, 1854, 3410) \rightarrow
</math>
<math>
\cdots \rightarrow
(0, 0, 128, 128) \rightarrow
(0, 128, 0, 128) \rightarrow
(128, 128, 128, 128) \rightarrow
(0, 0, 0, 0)
</math>

This 5-tuple sequence enters a period 15 binary 'loop' after 7 iterations.

<math>
\begin{matrix}
1 5 7 9 9 \rightarrow &
4 2 2 0 8 \rightarrow &
2 0 2 8 4 \rightarrow &
2 2 6 4 2 \rightarrow &
0 4 2 2 0 \rightarrow &
4 2 0 2 0 \rightarrow \\
2 2 2 2 4 \rightarrow &
0 0 0 2 2 \rightarrow &
0 0 2 0 2 \rightarrow &
0 2 2 2 2 \rightarrow &
2 0 0 0 2 \rightarrow &
2 0 0 2 0 \rightarrow \\
2 0 2 2 2 \rightarrow &
2 2 0 0 0 \rightarrow &
0 2 0 0 2 \rightarrow &
2 2 0 2 2 \rightarrow &
0 2 2 0 0 \rightarrow &
2 0 2 0 0 \rightarrow \\
2 2 2 0 2 \rightarrow &
0 0 2 2 0 \rightarrow &
0 2 0 2 0 \rightarrow &
2 2 2 2 0 \rightarrow &
0 0 0 2 2 \rightarrow &
\cdots \quad \quad \\
\end{matrix}
</math>

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:

<math>
\begin{matrix}
1 2 1 2 1 0 \rightarrow &
1 1 1 1 1 1 \rightarrow &
0 0 0 0 0 0 \\
\end{matrix}
</math>

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.<ref name="E.Miztani, A.Nozaki, T.Sawatari 2013">{{cite journal
| last1 = Euich
| first1 = Miztani
| last2 = Akihiro
| first2 = Nozaki.
| last3 = Toru
| first3 = Sawatari.
| title = A Conjecture of Ducci Sequences and the Aspects
| journal = RIMS Kokyuroku
| volume = 1873
| pages = 88–97
| year = 2013
| url = http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1873-14.pdf
| accessdate = 2014-02-18}}</ref>

==Modulo two form==
When the Ducci sequences enter binary loops, it is possible to treat the sequence in modulo two. That is:<ref name="Breauer">Florian Breuer, "Ducci sequences in higher dimensions" in INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007) [http://www.integers-ejcnt.org/h24/h24.pdf]</ref>
:<math>(|a_1-a_2|, |a_2-a_3|, ..., |a_n-a_1|)\ = (a_1+a_2, a_2+a_3, ..., a_n + a_1) \bmod 2</math>
This forms the basis for proving when the sequence vanish to all zeros.

==Cellular automata==
[[File:CA rule 102.png|140px|right]]
The linear map in modulo 2 can further be identified as the [[cellular automaton|cellular automata]] denoted as '''rule 102''' in [[Wolfram code]] and related to [[rule 90]] through the Martin-Odlyzko-Wolfram map.<ref>S Lettieri, JG Stevens, DM Thomas, "Characteristic and minimal polynomials of linear cellular automata" in Rocky Mountain J. Math, 2006.</ref><ref>M Misiurewicz, JG Stevens, DM Thomas, "Iterations of linear maps over finite fields", Linear Algebra and Its Applications, 2006</ref> Rule 102 reproduces the [[Sierpinski triangle]].<ref>Weisstein, Eric W. "Rule 102." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rule102.html</ref>

==Other related topics==
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.<ref>F. Breuer et al. 'Ducci-sequences and cyclotomic polynomials' in [[Finite Fields and Their Applications]] 13 (2007) 293–304</ref> While there are no practical applications of the Ducci map at present, its connection to the highly applied field of difference equations led <ref name="Brockman"/> to conjecture that a form of the Ducci map may also find application in the future.

==References==
{{reflist}}

==External links==
* [http://www.math.jussieu.fr/theses/2002/breuer/homepage/research.html Ducci Sequence] {{Webarchive|url=https://web.archive.org/web/20040826042516/http://www.math.jussieu.fr/theses/2002/breuer/homepage/research.html |date=2004-08-26 }}
* [http://www.cut-the-knot.org/SimpleGames/IntIter.shtml Integer Iterations on a Circle] at [[Cut-the-Knot]]

{{DEFAULTSORT:Ducci Sequence}}
[[Category:Sequences and series]]
[[Category:Number theory]]

Ducci sequence - Revision history

imported>Citation bot: Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Sequences and series | #UCB_Category 32/47