user
When counting integers in binary, if you put a (binary) point to the right of the count then the column immediately to the left denotes a digit with a multiplier of 

2

0
{\displaystyle {\displaystyle 2^{0}}}
; the digit in the next column to the left has a multiplier of 

2

1
{\displaystyle {\displaystyle 2^{1}}}
; and so on.

So in the following table:

```
  0.
  1.
 10.
 11.
 ...
```

the binary number "`10`" is 

1
×

2

1
+
0
×

2

0
{\displaystyle {\displaystyle 1\times 2^{1}+0\times 2^{0}}}
.

You can also have binary digits to the right of the “point”, just as in the decimal number system. In that case, the digit in the place immediately to the right of the point has a weight of 

2

−
1
{\displaystyle {\displaystyle 2^{-1}}}
, or 

1

/
2
{\displaystyle {\displaystyle 1/2}}
.
The weight for the second column to the right of the point is 

2

−
2
{\displaystyle {\displaystyle 2^{-2}}}
 or 

1

/
4
{\displaystyle {\displaystyle 1/4}}
. And so on.

If you take the integer binary count of the first table, and *reflect* the digits about the binary point, you end up with **the van der Corput sequence of numbers in base 2**.

```
  .0
  .1
  .01
  .11
  ...
```

The third member of the sequence, binary `0.01`, is therefore 

0
×

2

−
1
+
1
×

2

−
2
{\displaystyle {\displaystyle 0\times 2^{-1}+1\times 2^{-2}}}
 or 

1

/
4
{\displaystyle {\displaystyle 1/4}}
.

Distribution of 2500 points each: Van der Corput (top) vs pseudorandom

Members of the sequence lie within the interval

0
≤
x
<
1
{\displaystyle {\displaystyle 0\leq x<1}}

. Points within the sequence tend to be evenly distributed which is a useful trait to have for Monte Carlo simulations.

This sequence is also a superset of the numbers representable by the "fraction" field of an old IEEE floating point standard. In that standard, the "fraction" field represented the fractional part of a binary number beginning with "1." e.g. 1.101001101.

**Hint**

A *hint* at a way to generate members of the sequence is to modify a routine used to change the base of an integer:

```
>>> def base10change(n, base):
	digits = []
	while n:
		n,remainder = divmod(n, base)
		digits.insert(0, remainder)
	return digits

>>> base10change(11, 2)
[1, 0, 1, 1]

```

the above showing that `11` in decimal is 

1
×

2

3
+
0
×

2

2
+
1
×

2

1
+
1
×

2

0
{\displaystyle {\displaystyle 1\times 2^{3}+0\times 2^{2}+1\times 2^{1}+1\times 2^{0}}}
.  
Reflected this would become `.1101` or 

1
×

2

−
1
+
1
×

2

−
2
+
0
×

2

−
3
+
1
×

2

−
4
{\displaystyle {\displaystyle 1\times 2^{-1}+1\times 2^{-2}+0\times 2^{-3}+1\times 2^{-4}}}

Task description

* Create a function/method/routine that given *n*, generates the *n'*th term of the van der Corput sequence in base 2.
* Use the function to compute *and display* the first ten members of the sequence. (The first member of the sequence is for *n*=0).

* As a stretch goal/extra credit, compute and show members of the sequence for bases other than 2.

See also

* The Basic Low Discrepancy Sequences
* Non-decimal radices/Convert
* Van der Corput sequence
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2020.08.1

First a cheap implementation in base 2, using string operations.

```
constant VdC = map { :2("0." ~ .base(2).flip) }, ^Inf;
.say for VdC[^16];

```

Here is a more elaborate version using the polymod built-in integer method:

```
sub VdC($base = 2) {
    map {
        [+] $_ && .polymod($base xx *) Z/ [\*] $base xx *
    }, ^Inf
}

.say for VdC[^10];

```

Output:

```
0
0.5
0.25
0.75
0.125
0.625
0.375
0.875
0.0625
0.5625
```

Here is a fairly standard imperative version in which we mutate three variables in parallel:

```
sub vdc($num, $base = 2) {
    my $n = $num;
    my $vdc = 0;
    my $denom = 1;
    while $n {
        $vdc += $n mod $base / ($denom *= $base);
        $n div= $base;
    }
    $vdc;
}

for 2..5 -> $b {
    say "Base $b";
    say ( vdc($_,$b).Rat.nude.join('/') for ^10 ).join(', ');
    say '';
}

```

Output:

```
Base 2
0, 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16

Base 3
0, 1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9, 1/27

Base 4
0, 1/4, 1/2, 3/4, 1/16, 5/16, 9/16, 13/16, 1/8, 3/8

Base 5
0, 1/5, 2/5, 3/5, 4/5, 1/25, 6/25, 11/25, 16/25, 21/25
```

Here is a functional version that produces the same output:

```
sub vdc($value, $base = 2) {
    my @values = $value, { $_ div $base } ... 0;
    my @denoms = $base,  { $_  *  $base } ... *;
    [+] do for (flat @values Z @denoms) -> $v, $d {
        $v mod $base / $d;
    }
}

```

We first define two sequences, one finite, one infinite.
When we zip those sequences together, the finite sequence terminates the loop (which, since a Raku loop returns all its values, is merely another way of writing a map).
We then sum with [+], a reduction of the + operator.
(We could have in-lined the sequences or used a traditional map operator, but this way seems more readable than the typical FP solution.)
The do is necessary to introduce a statement where a term is expected, since Raku distinguishes "sentences" from "noun phrases" as a natural language might.