Van der Corput sequences

This article page is a stub, please help by expanding it.

A van der Corput sequence is a low-discrepancy sequence over the unit interval first published in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base b representation of the sequence of natural numbers (0, 1, 2, 3, ...), where 0 is often not included.

The elements of the van der Corput sequence (in any base) form a dense set in the unit interval: for any real number in [0, 1] there exists a subsequence of the van der Corput sequence that converges towards that number. They are also equidistributed (maximally self-avoiding) over the unit interval.

Binary van der Corput sequence

The binary van der Corput sequence can be written as

{0₂, 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₂, ...}

or, in fractional form, as

$\{{\tfrac {0}{1}},{\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 \}\,$

where the numerators, except for the first term, are necessarily odd, while the denominators are powers of two, thus coprime, and all the above fractions are already in reduced form.

The numerators give the sequence (Cf. A030101) (look at the graph for the nice equidistribution patterns)

{0, 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 13, 3, 11, 7, 15, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19, 51, 11, 43, 27, 59, 7, 39, 23, 55, 15, 47, 31, 63, 1, 65, 33, 97, 17, 81, 49, 113, 9, ...}

The denominators give the sequence (Cf. A062383, where $\scriptstyle 2^{n},\,n\,\geq \,1,\,$ appears $\scriptstyle 2^{n-1}\,$ times in a row)

{1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, ...}

Ternary van der Corput sequence

The ternary van der Corput sequence can be written as

{0₃, 0.1₃, 0.2₃, 0.01₃, 0.11₃, 0.21₃, 0.02₃, 0.12₃, 0.22₃, 0.001₃, 0.101₃, 0.201₃, 0.011₃, 0.111₃, 0.211₃, 0.021₃, ...}

or, in fractional form, as

$\{{\tfrac {0}{1}},{\tfrac {1}{3}},{\tfrac {2}{3}},{\tfrac {1}{9}},{\tfrac {4}{9}},{\tfrac {7}{9}},{\tfrac {2}{9}},{\tfrac {5}{9}},{\tfrac {8}{9}},{\tfrac {1}{27}},{\tfrac {10}{27}},{\tfrac {19}{27}},{\tfrac {4}{27}},{\tfrac {13}{27}},{\tfrac {22}{27}},{\tfrac {7}{27}},\ldots \}\,$

where the numerators give the sequence (Cf. A030102) (look at the graph for the nice equidistribution patterns)

{0, 1, 2, 1, 4, 7, 2, 5, 8, 1, 10, 19, 4, 13, 22, 7, 16, 25, 2, 11, 20, 5, 14, 23, 8, 17, 26, 1, 28, 55, 10, 37, 64, 19, 46, 73, 4, 31, 58, 13, 40, 67, 22, 49, 76, 7, 34, 61, 16, 43, 70, 25, 52, 79, 2, 29, 56, 11, 38, 65, 20, 47, 74, 5, 32, 59, 14, 41, 68, 23, 50, 77, ...}

and the denominators give the sequence (Cf. A064235, where $\scriptstyle 3^{n},\,n\,\geq \,1\,$, appears $\scriptstyle 2\cdot 3^{n-1}\,$ times in a row)

{1, 3, 3, 9, 9, 9, 9, 9, 9, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, ...}

Decimal van der Corput sequence

The decimal van der Corput sequence can be written as

{0, 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, ...}

or, in nonreduced fractional form, as

$\{{\tfrac {0}{1}},{\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 \}\,$

where the numerators give the sequence (Cf. A004086) (look at the graph for the nice equidistribution patterns)

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 21, 31, 41, 51, 61, 71, 81, 91, 2, 12, 22, 32, 42, 52, 62, 72, 82, 92, 3, 13, 23, 33, 43, 53, 63, 73, 83, 93, 4, 14, 24, 34, 44, 54, 64, 74, 84, 94, 5, 15, 25, 35, 45, 55, 65, 75, 85, 95, 6, ...}

and the denominators give the sequence (Cf. A??????, where $\scriptstyle 10^{n},\,n\,\geq \,1\,$, appears $\scriptstyle 9\cdot 10^{n-1}\,$ times in a row)

{1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, ...}

In reduced fractional form, we get

$\{{\tfrac {0}{1}},{\tfrac {1}{10}},{\tfrac {1}{5}},{\tfrac {3}{10}},{\tfrac {2}{5}},{\tfrac {1}{2}},{\tfrac {3}{5}},{\tfrac {7}{10}},{\tfrac {4}{5}},{\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 {1}{50}},{\tfrac {3}{25}},{\tfrac {11}{50}},{\tfrac {8}{25}},\ldots \}\,$

where the numerators give the sequence (Cf. A??????)

{0, 1, 1, 3, 2, 1, 3, 7, 4, 9, 1, 11, 21, 31, 41, 51, 61, 71, 81, 91, 1, 3, 11, 8, ...}

and the denominators give the sequence (Cf. A??????)

{1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 50, 25, 50, 25, ...}

See also

• Constructions of low-discrepancy sequences

References

• J. G. van der Corput, Verteilungsfunktionen. Proc. Ned. Akad. v. Wet., 38:813–821, 1935.
• Kuipers, L.; Niederreiter, H. (2005), Uniform distribution of sequences, Dover Publications, p. 129,158, ISBN 0-486-45019-8 ..

External links

• Weisstein, Eric W., Van der Corput sequence, from MathWorld—A Wolfram Web Resource.