ファンデルコルプト数列

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

自然数nのb-進表記は、

であり、k桁目のdkは0 ≤ dk(n) < bを満たす。
このとき、ファンデルコルプト数列のn項目であるgb(n)は

である。

例 
例えば、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進）は

と続き、小数表記では
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進ファンデルコルプト数列は

または
0.12, 0.012, 0.112, 0.0012, 0.1012, 0.0112, 0.1112, 0.00012, 0.10012, 0.01012, 0.11012, 0.00112, 0.10112, 0.01112, 0.11112, …
と続く。

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

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

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

参考文献

外部リンク
 Van der Corput sequence at MathWorld

乱数
数列
数学に関する記事
数学のエポニム