Последовательность Ван дер Корпута

Последовательность Ван дер Корпута является примером простейшей одномерной последовательности с низким расхождением на единичном интервале ; Впервые оно было описано в 1935 году голландским математиком Дж. Г. ван дер Корпутом . Он строится путем обращения по основанию n представления последовательности натуральных чисел (1, 2, 3, …).

The $b$ -арное представление натурального числа $n\geq 1$ является $n~=~\sum _{k=0}^{L-1}d_{k}(n)b^{k}~=~d_{0}(n)b^{0}+\cdots +d_{L-1}(n)b^{L-1},$ где $b$ – это основание, в котором находится число $n$ представлено, и $0\leq d_{k}(n)<b;$ то есть $k$ -я цифра в $b$ -арное расширение $n.$ $n$ -е число в последовательности Ван дер Корпута $g_{b}(n)~=~\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}~=~d_{0}(n)b^{-1}+\cdots +d_{L-1}(n)b^{-L}.$

Примеры [ править ]

Например, чтобы получить десятичную последовательность Ван дер Корпута, мы начинаем с деления чисел от 1 до 9 на десятые доли ( $x/10$ ), затем меняем знаменатель на 100, чтобы начать деление в сотых долях ( $x/100$ ). Что касается числителя, мы начинаем со всех двузначных чисел от 10 до 99, но в обратном порядке цифр. Следовательно, мы получим числители, сгруппированные по конечной цифре. Во-первых, все двузначные числители, оканчивающиеся на 1, поэтому следующие числители — 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Затем числители, оканчивающиеся на 2, то есть 02, 12. , 22, 32, 42, 52, 62, 72, 82, 92. И после этого числители оканчиваются на 3: 03, 13, 23 и так далее...

Таким образом, последовательность начинается $\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\},$ или в десятичном представлении:

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

То же самое можно сделать и для двоичной системы счисления , а двоичная последовательность Ван дер Корпута имеет вид

0.1 ₂, 0.01 ₂, 0.11 ₂, 0.001 ₂, 0.101 ₂, 0.011 ₂, 0.111 ₂, 0.0001 ₂, 0.1001 ₂, 0.0101 ₂, 0.1101 ₂, 0.0011 ₂, 0.1011 ₂, 0.0111 ₂, 0.1111 ₂, …

или, что то же самое, ${\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 .$

Элементы последовательности Ван дер Корпута (в любой базе) образуют плотное множество на единичном интервале; то есть для любого действительного числа в $[0,1]$ , существует подпоследовательность последовательности Ван дер Корпута, которая сходится к этому числу. Они также равномерно распределены по единичному интервалу.

Реализация на языке C [ править ]

double corput(int n, int base){
    double q=0, bk=(double)1/base;

    while (n > 0) {
      q += (n % base)*bk;
      n /= base;
      bk /= base;
    }

    return q;
}

См. также [ править ]

Перестановка с обращением битов - перестановка, которая меняет двоичные числа.
Построение последовательностей с низким расхождением – тип математической последовательности.
Последовательность Холтона - тип числовой последовательности, используемый в статистике, естественное обобщение последовательности Ван дер Корпута на более высокие измерения.

Ссылки [ править ]

ван дер Корпут, JG (1935), «Функции распределения (первое общение)» (PDF) , Proceedings of Koninklijke Akademie van Wetenschappen te Amsterdam (на немецком языке), 38 : 813–821, Zbl 0012.34705
Койперс, Л.; Нидеррайтер, Х. (2005) [1974], Равномерное распределение последовательностей , Dover Publications , стр. 129 158, ISBN 0-486-45019-8 , Збл 0281.10001

Внешние ссылки [ править ]

Последовательность Ван дер Корпута в MathWorld