ファンデルコルプト数列のソースを表示

[[File:Van_der_Corput_sequence_999.svg|thumb|330px|0から1の単位区間（横軸）を充填していく、最初''n''項のファンデルコルプト数列（上から順に''n''が 0 から 999 へと増加し、色が濃くなっている。]]

'''ファンデルコルプト数列'''（'''van der Corput sequence'''）は、[[単位区間]]に対する{{ill2|超一様分布列|en|low-discrepancy sequence}}（準乱数列）の1つであり、1935年にオランダの数学者ヨハネ・ファン・デル・コルプトによって考案された。この数列は[[自然数]]の''n''進表記を逆順にしたものを小数点以下に並べたものである。

自然数''n''の''b''-進表記は、
:<math>
n=\sum_{k=0}^{L-1}d_k(n)b^k
</math>
であり、''k''桁目の''d''<sub>''k''</sub>は0 ≤ ''d''<sub>''k''</sub>(''n'') < ''b''を満たす。
このとき、ファンデルコルプト数列の''n''項目である''g''<sub>''b''</sub>(n)は
:<math>
g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}
</math>
である。

== 例 ==
例えば、10進のファンデルコルプト数列を得るためには、まず 1 から 9 を10で割ったものを並べる (''x''/10)。そして、分母を100として、分子に 10 から 99 を並べる。しかしここで、10 からそのまま並べるのではなく、01, 11, 21, 31, 41, 51, 61, 71, 81, 91 ... というように、10の位と1の位を入れ替えて並べる。そして、20以降は分子が2で終わる数字が続き、 02, 12, 22, 32, 42, 52, 62, 72, 82, 92、更に 03, 13, 23 ... と続く。

そのため、ファンデルコルプト数列（10進）は
:<math>\left\{ \tfrac{1}{10}, \tfrac{2}{10}, \tfrac{3}{10}, \tfrac{4}{10}, \tfrac{5}{10}, \tfrac{6}{10}, \tfrac{7}{10}, \tfrac{8}{10}, \tfrac{9}{10}, \tfrac{1}{100}, \tfrac{11}{100}, \tfrac{21}{100}, \tfrac{31}{100}, \tfrac{41}{100}, \tfrac{51}{100}, \tfrac{61}{100}, \tfrac{71}{100}, \tfrac{81}{100}, \tfrac{91}{100}, \tfrac{2}{100}, \tfrac{12}{100}, \tfrac{22}{100}, \tfrac{32}{100}, \ldots \right\}</math>
と続き、[[小数]]表記では
:0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, …
となる。

[[二進法|2進法]]でも同様であり、2進ファンデルコルプト数列は
:<math>\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{3}{4}, \tfrac{1}{8}, \tfrac{5}{8}, \tfrac{3}{8}, \tfrac{7}{8}, \tfrac{1}{16}, \tfrac{9}{16}, \tfrac{5}{16}, \tfrac{13}{16}, \tfrac{3}{16}, \tfrac{11}{16}, \tfrac{7}{16}, \tfrac{15}{16}, \ldots</math>
または
:0.1<sub>2</sub>, 0.01<sub>2</sub>, 0.11<sub>2</sub>, 0.001<sub>2</sub>, 0.101<sub>2</sub>, 0.011<sub>2</sub>, 0.111<sub>2</sub>, 0.0001<sub>2</sub>, 0.1001<sub>2</sub>, 0.0101<sub>2</sub>, 0.1101<sub>2</sub>, 0.0011<sub>2</sub>, 0.1011<sub>2</sub>, 0.0111<sub>2</sub>, 0.1111<sub>2</sub>, …
と続く。

任意の底において、ファンデルコルプト数列は単位区間での[[稠密集合]]となる。つまり、[0, 1]内の任意の[[実数]]に対して、その実数に[[数列の極限|収束]]するファンデルコルプト数列の部分列が存在する。また、単位区間で一様である。

==C での実装==
<syntaxhighlight lang="c">
double corput(int n, int base){
  double q = 0;
  double bk = 1.0 / base;
  while (n > 0) {
    q += (n % base) * bk;
    n /= base;
    bk /= base;
  }
  return q;
}
</syntaxhighlight>

==関連項目==
* ビット反転順
* [[ハルトン数列]]：高次元へのファンデルコルプト数列の拡張
* [[モンテカルロ法]]：準モンテカルロ法により、収束が早い場合がある

==参考文献==
* {{citation | last=van der Corput | first=J.G. | authorlink=Johannes van der Corput | title=Verteilungsfunktionen (Erste Mitteilung) | language=German | zbl=0012.34705 | journal=Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam | volume=38 | pages=813–821 | year=1935 | url=http://www.dwc.knaw.nl/DL/publications/PU00014607.pdf }}
* {{citation | last=Kuipers | first=L. | last2= Niederreiter | first2=H. | author2-link = Harald Niederreiter | title = Uniform distribution of sequences | publisher=[[Dover Publications]] | year=2005 | origyear=1974 | isbn=0-486-45019-8 | page=129,158 | zbl=0281.10001 }}

==外部リンク==
* [http://mathworld.wolfram.com/vanderCorputSequence.html Van der Corput sequence] at [[MathWorld]]
{{デフォルトソート:ふあんてるこるふとすうれつ}}
[[Category:乱数]]
[[Category:数列]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]