ドゥッチ数列のソースを表示

'''ドゥッチ数列'''（ドゥッチすうれつ）とは、n組の[[整数]]の元からなる[[数列]]で、例えば
<math>(a_1,a_2,...,a_n)</math>
の整数からなる数列があり、隣合う2つの整数の差の絶対値(最後尾の整数は最初の整数との差を取った絶対値)を各元とする数列:
:<math>(a_1,a_2,...,a_n) \rightarrow (|a_1-a_2|, |a_2-a_3|, ..., |a_n-a_1|)\, .</math>
の事を意味する。別の言い方をすれば、まず輪に配列されたn個の異なる正の整数の組があり、各隣合う2つの整数の差の絶対値をとってできた、新たな正の整数が配列された輪の組を意味する。またこの操作を繰り返してできる数列の組全体も同様にドゥッチ数列と見なす。
ドゥッチ数列と言う名称は、その数列の(性質の)発見者でもあるイタリア人数学者の名にちなんで名付けられた。ドゥッチ数列は(海外では)'''ドゥッチ写像'''あるいは'''Nナンバー・ゲーム'''とも呼ばれており、これに関する多くの未解決の問題が残されている。<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 | publisher = [[:en:Taylor & Francis]] | location = London | year = 2004 | url = http://www.math.grinnell.edu/~chamberl/papers/ducci_survey.pdf | accessdate = 2009-01-26}}</ref>

== 特性 ==
一回以上の上記の再帰操作後の数列について、どの数列の元の整数も0以上か、または（最初のこれらの操作を始める以前の）初期の数列の各元の整数の最小値以上あるいは最大値以下となる。有限個の元からなるドゥッチ数列にこうした条件で再帰操作を繰り返すうちに、既に以前再帰計算中に現れたものと整数の種類とその配列順序が全く同じ数列がいずれ現れる。そのためドゥッチ数列はその再帰操作に[[周期性]]を持つ。
またもしｎが2のべき乗であれば、有限回の再帰操作でその数列は必ず(0,0,...,0)となる。
逆にもしｎが2のべき乗でないのであれば、全ての元が0の数列になるか、全ての元が0と1のみからなるか、あるいは異なる2種類の正の整数からなる数列となる（つまり何度再帰操作を繰り返しても全ての元が0とならない）。
ドゥッチ数列の一般化としては、各元を整数に限定せず、当然ながら実数に範囲を広げることもできる。この場合、先に書いた２のべき乗に関する全ての元が0となる性質は現れない。例えばqが[[多項式]]<math>x^3 - x^2 - x - 1 = 0</math>の正の無理数の根で、(1, ''q'', ''q''<sup>2</sup>, ''q''<sup>3</sup>)のようなドゥッチ数列は有限回の再帰操作で(0,0,0,0)とはならない（但し無限回再帰操作を繰り返すと(0,0,0,0)に収束する）。<ref name="Brockman">{{cite journal | last1 = Brockman | first1 = Greg | title = Asymptotic behaviour of certain Ducci sequences | journal = [[:en:Fibonacci Quarterly]] | url = http://www.cut-the-knot.org/Curriculum/Algebra/GregBrockman/GregBrockmanDucciSequencesPaper.pdf |format=PDF | year = 2007}} </ref>

== 例 ==
ドゥッチ数列は全ての元が0になるか再帰操作が上記で述べた周期性に入るまでには再帰操作の回数が非常に多くなることもある。例えば(0, 653, 1854, 4063)から再帰操作を始めた場合、全ての元が0になるのに24回の再帰操作を要する。

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

以下の5つの元からなるドゥッチ数列は、7回目の再帰計算で元が二種類だけとなり、16回の操作を経て7回目の結果に戻るのでループし、いわば周期性を持っている。

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


また次のような6つの正の整数の元からなるドゥッチ数列、つまり2のべき乗でない数列であっても、有限回の再帰操作で全ての元が0になる場合もある。

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

更に2のべき乗の数列にいくつかの条件を与えることにより、再帰操作が2のべき乗のステップで終わり得る。加えて、そうした条件によって２のべき乗の再帰操作で終わるドゥッチ数列の数には法則性があることが予想される。.<ref name="E.Miztani, A.Nozaki, T.Sawatari 2013">{{cite journal|和書
 |author=水谷雄一
 |author2=野崎昭弘
 |author3=澤渡徹
 |title=A Conjecture of Ducci Sequences and the Aspects
 |journal=数理解析研究所講究録
 |ISSN=1880-2818
 |publisher=京都大学数理解析研究所
 |date=2014-01
 |volume=1873
 |pages=88-97
 |CRID=1050845760738234752}}</ref>

== 2進法の場合 ==
再帰操作の過程で全ての元が0と1からなるドゥッチ数列となり、再帰操作が周期性を持つに到った場合、以下のように数列の各元を法が2の[[合同式]]に置き換える事ができる。<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)\ mod 2</math>

この事についてはドゥッチ数列の全ての元が0になる場合を証明する際の基礎となる。

== セル・オートマトン ==
[[File:Sierpiński triangle.svg|thumb|シェルピンスキーのギャスケット]]
2進数での写像は、[[:en:Wolfram code]]の[[:en:Rule 102]]という形で、[[セル・オートマトン]]として認識されている。またこれは、Martin-Odlyzko-Wolfram 図を通じて、[[:en:Rule 90]]とも関連性を持つ。<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> [[:en:Rule 102]]は[[シェルピンスキーのギャスケット]]を再生する。<ref>Weisstein, Eric W. "Rule 102." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rule102.html</ref>

== 関連する概念 ==
ドゥッチ数列は[[差分方程式]]の例で、[[非線形力学]]、[[カオス理論]]、[[数値解析]]の分野にも属する。また[[円分多項式]]との関連も指摘されている。<ref>F. Breuer et al. 'Ducci-sequenc　es and cyclotomic polynomials' in [[:en:Finite Fields and Their Applications]] 13 (2007) 293?304</ref>　現時点ではドゥッチ数列の実践的な応用例はないが、差分方程式のより高度な応用分野との関連付けにより、将来ドゥッチ写像のある形式がそうした応用例を見つけ得る可能性が推測される。<ref name="Brockman"/>

== 参考文献 ==
{{reflist}} 

== 外部リンク ==
* [http://www.math.jussieu.fr/theses/2002/breuer/homepage/research.html Ducci Sequence] 
* [http://www.cut-the-knot.org/SimpleGames/IntIter.shtml Integer Iterations on a Circle] at [[:en:Cut-the-Knot]] 

{{DEFAULTSORT:とうつちすうれつ}} 
[[Category:数論]]
[[Category:数列]]
[[Category:数学に関する記事]]