This site is supported by donations to The OEIS Foundation.
Van der Corput sequences
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.
Contents
Binary van der Corput sequence
The binary van der Corput sequence can be written as
- {02, 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, ...}
or, in fractional form, as
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 appears 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
- {03, 0.13, 0.23, 0.013, 0.113, 0.213, 0.023, 0.123, 0.223, 0.0013, 0.1013, 0.2013, 0.0113, 0.1113, 0.2113, 0.0213, ...}
or, in fractional form, as
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 , appears 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
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 , appears 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
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
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.