PROFILPELAJAR.COM

ドゥッチ数列（ドゥッチすうれつ）とは、n組の整数の元からなる数列で、例えば $(a_{1},a_{2},...,a_{n})$ の整数からなる数列があり、隣合う2つの整数の差の絶対値(最後尾の整数は最初の整数との差を取った絶対値)を各元とする数列:

(a_{1},a_{2},...,a_{n})\rightarrow (|a_{1}-a_{2}|,|a_{2}-a_{3}|,...,|a_{n}-a_{1}|)\,.

の事を意味する。別の言い方をすれば、まず輪に配列されたn個の異なる正の整数の組があり、各隣合う2つの整数の差の絶対値をとってできた、新たな正の整数が配列された輪の組を意味する。またこの操作を繰り返してできる数列の組全体も同様にドゥッチ数列と見なす。ドゥッチ数列と言う名称は、その数列の(性質の)発見者でもあるイタリア人数学者の名にちなんで名付けられた。ドゥッチ数列は(海外では)ドゥッチ写像あるいはNナンバー・ゲームとも呼ばれており、これに関する多くの未解決の問題が残されている。^[1]

特性

一回以上の上記の再帰操作後の数列について、どの数列の元の整数も0以上か、または（最初のこれらの操作を始める以前の）初期の数列の各元の整数の最小値以上あるいは最大値以下となる。有限個の元からなるドゥッチ数列にこうした条件で再帰操作を繰り返すうちに、既に以前再帰計算中に現れたものと整数の種類とその配列順序が全く同じ数列がいずれ現れる。そのためドゥッチ数列はその再帰操作に周期性を持つ。またもしｎが2のべき乗であれば、有限回の再帰操作でその数列は必ず(0,0,...,0)となる。逆にもしｎが2のべき乗でないのであれば、全ての元が0の数列になるか、全ての元が0と1のみからなるか、あるいは異なる2種類の正の整数からなる数列となる（つまり何度再帰操作を繰り返しても全ての元が0とならない）。ドゥッチ数列の一般化としては、各元を整数に限定せず、当然ながら実数に範囲を広げることもできる。この場合、先に書いた２のべき乗に関する全ての元が0となる性質は現れない。例えばqが多項式 $x^{3}-x^{2}-x-1=0$ の正の無理数の根で、(1, q, q², q³)のようなドゥッチ数列は有限回の再帰操作で(0,0,0,0)とはならない（但し無限回再帰操作を繰り返すと(0,0,0,0)に収束する）。^[2]

例

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

$(0,653,1854,4063)\rightarrow (653,1201,2209,4063)\rightarrow (548,1008,1854,3410)\rightarrow$ $\cdots \rightarrow (0,0,128,128)\rightarrow (0,128,0,128)\rightarrow (128,128,128,128)\rightarrow (0,0,0,0)$

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

${\begin{matrix}15799\rightarrow &42208\rightarrow &20284\rightarrow &22642\rightarrow &04220\rightarrow &42020\rightarrow \\22224\rightarrow &00022\rightarrow &00202\rightarrow &02222\rightarrow &20002\rightarrow &20020\rightarrow \\20222\rightarrow &22000\rightarrow &02002\rightarrow &22022\rightarrow &02200\rightarrow &20200\rightarrow \\22202\rightarrow &00220\rightarrow &02020\rightarrow &22220\rightarrow &00022\rightarrow &\cdots \quad \quad \\\end{matrix}}$

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

${\begin{matrix}121210\rightarrow &111111\rightarrow &000000\\\end{matrix}}$

更に2のべき乗の数列にいくつかの条件を与えることにより、再帰操作が2のべき乗のステップで終わり得る。加えて、そうした条件によって２のべき乗の再帰操作で終わるドゥッチ数列の数には法則性があることが予想される。.^[3]

2進法の場合

再帰操作の過程で全ての元が0と1からなるドゥッチ数列となり、再帰操作が周期性を持つに到った場合、以下のように数列の各元を法が2の合同式に置き換える事ができる。^[4] $(|a_{1}-a_{2}|,|a_{2}-a_{3}|,...,|a_{n}-a_{1}|)\ =(a_{1}+a_{2},a_{2}+a_{3},...,a_{n}+a_{1})\ mod2$

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

セル・オートマトン

2進数での写像は、en:Wolfram codeのen:Rule 102という形で、セル・オートマトンとして認識されている。またこれは、Martin-Odlyzko-Wolfram 図を通じて、en:Rule 90とも関連性を持つ。^[5]^[6] en:Rule 102はシェルピンスキーのギャスケットを再生する。^[7]

参考文献

^ Chamberland, Marc; Thomas, Diana M. (2004). “The N-Number Ducci Game”. Journal of Difference Equations and Applications (London: en:Taylor & Francis) 10 (3): 33?36 2009年1月26日閲覧。.
^ ^a ^b Brockman, Greg (2007). “Asymptotic behaviour of certain Ducci sequences” (PDF). en:Fibonacci Quarterly.
^ 水谷雄一、野崎昭弘、澤渡徹「A Conjecture of Ducci Sequences and the Aspects」『数理解析研究所講究録』第1873巻、京都大学数理解析研究所、2014年1月、88-97頁、CRID 1050845760738234752、ISSN 1880-2818。
^ 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-sequenc　es and cyclotomic polynomials' in en:Finite Fields and Their Applications 13 (2007) 293?304