Последовательность Ван дер Корпута - Van der Corput sequence

Иллюстрация заполнения единичного интервала (горизонтальная ось) с помощью первого п члены десятичной последовательности Ван дер Корпута, для п от 0 до 999 (вертикальная ось)

А последовательность ван дер Корпута является примером простейшего одномерного последовательность с низким расхождением над единичный интервал; он был впервые описан в 1935 г. нидерландский язык математик J. G. van der Corput. Он построен путем обращения основание-п представление последовательности натуральные числа (1, 2, 3, …).

В б-арное представление положительного целого числа п (≥ 1) является

${displaystyle n=sum _{k=0}^{L-1}d_{k}(n)b^{k},}$

куда б это база, в которой число п представлен, а 0 ≤ d_k(п) < б, т.е. k-я цифра в б-арное расширение п. п-е число в последовательности Ван дер Корпута равно

${displaystyle g_{b}(n)=sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}.}$

Примеры

Например, чтобы получить десятичный Ван дер Корпута, мы начинаем с деления чисел от 1 до 9 на десятые (Икс/ 10), затем меняем знаменатель на 100, чтобы начать деление на сотые (Икс/ 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 и так далее ...

Таким образом, последовательность начинается

${displaystyle left{{ frac {1}{10}},{ frac {2}{10}},{ frac {3}{10}},{ frac {4}{10}},{ frac {5}{10}},{ frac {6}{10}},{ frac {7}{10}},{ frac {8}{10}},{ frac {9}{10}},{ frac {1}{100}},{ frac {11}{100}},{ frac {21}{100}},{ frac {31}{100}},{ frac {41}{100}},{ frac {51}{100}},{ frac {61}{100}},{ frac {71}{100}},{ frac {81}{100}},{ frac {91}{100}},{ frac {2}{100}},{ frac {12}{100}},{ frac {22}{100}},{ frac {32}{100}},ldots ight},}$

или в десятичном представлении:

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

или, что то же самое,

${displaystyle { frac {1}{2}},{ frac {1}{4}},{ frac {3}{4}},{ frac {1}{8}},{ frac {5}{8}},{ frac {3}{8}},{ frac {7}{8}},{ frac {1}{16}},{ frac {9}{16}},{ frac {5}{16}},{ frac {13}{16}},{ frac {3}{16}},{ frac {11}{16}},{ frac {7}{16}},{ frac {15}{16}},ldots .}$

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

C реализация

двойной корпорация(int п, int основание){    двойной q=0, bk=(двойной)1/основание;    пока (п > 0) {      q += (п % основание)*bk;      п /= основание;      bk /= основание;    }    возвращаться q;}

Смотрите также

• Перестановка с обращением битов
• Конструкции последовательностей с малым расхождением
• Последовательность Холтона, естественное обобщение последовательности Ван дер Корпута на высшие размерности

Рекомендации

• ван дер Корпут, J.G. (1935), "Verteilungsfunktionen (Erste Mitteilung)" (PDF), Труды Koninklijke Akademie van Wetenschappen te Amsterdam (на немецком), 38: 813–821, Zbl  0012.34705
• Kuipers, L .; Нидеррайтер, Х. (2005) [1974], Равномерное распределение последовательностей, Dover Publications, п. 129 158, ISBN  0-486-45019-8, Zbl  0281.10001

внешняя ссылка

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