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

Иллюстрация заполнения единичного интервала (горизонтальная ось) с помощью первого п члены десятичной последовательности Ван дер Корпута, для п от 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