ドゥッチ数列

ドゥッチ数列（ドゥッチすうれつ）とは、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ナンバー・ゲームとも呼ばれており、これに関する多くの未解決の問題が残されている。

特性

一回以上の上記の再帰操作後の数列について、どの数列の元の整数も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)に収束する）。

例

ドゥッチ数列は全ての元が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のべき乗のステップで終わり得る。加えて、そうした条件によって２のべき乗の再帰操作で終わるドゥッチ数列の数には法則性があることが予想される。.

2進法の場合

再帰操作の過程で全ての元が0と1からなるドゥッチ数列となり、再帰操作が周期性を持つに到った場合、以下のように数列の各元を法が2の合同式に置き換える事ができる。 $(|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とも関連性を持つ。 en:Rule 102はシェルピンスキーのギャスケットを再生する。

関連する概念

ドゥッチ数列は差分方程式の例で、非線形力学、カオス理論、数値解析の分野にも属する。また円分多項式との関連も指摘されている。　現時点ではドゥッチ数列の実践的な応用例はないが、差分方程式のより高度な応用分野との関連付けにより、将来ドゥッチ写像のある形式がそうした応用例を見つけ得る可能性が推測される。

外部リンク

• Ducci Sequence
• Integer Iterations on a Circle at en:Cut-the-Knot