Van der Corput sequence

Van der Corput sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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⁰; the next column to the lefts digit has a multiplier of 2¹ and so on.

So in the following table:

  0.
  1.
 10.
 11.
 ...

The binary number "10" is $1 \times 2^1 + 0 \times 2^0$.

You can have binary digits to the right of the “point” just as in the decimal number system too. in this case, the digit in the place immediately to the right of the point has a weight of 2 ^{− 1}, or 1 / 2. The weight for the second column to the right of the point is 2 ^{− 2} or 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 \times 2^{-1} + 1 \times 2^{-2}$ or 1 / 4.

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

Members of the sequence lie within the interval $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\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0$.
Reflected this would become .1101 or $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

Ada

with Ada.Text_IO;
 
procedure Main is
   package Float_IO is new Ada.Text_IO.Float_IO (Float);
   function Van_Der_Corput (N : Natural; Base : Positive := 2) return Float is
      Value    : Natural  := N;
      Result   : Float    := 0.0;
      Exponent : Positive := 1;
   begin
      while Value > 0 loop
         Result   := Result +
                     Float (Value mod Base) / Float (Base ** Exponent);
         Value    := Value / Base;
         Exponent := Exponent + 1;
      end loop;
      return Result;
   end Van_Der_Corput;
begin
   for Base in 2 .. 5 loop
      Ada.Text_IO.Put ("Base" & Integer'Image (Base) & ":");
      for N in 1 .. 10 loop
         Ada.Text_IO.Put (' ');
         Float_IO.Put (Item => Van_Der_Corput (N, Base), Exp => 0);
      end loop;
      Ada.Text_IO.New_Line;
   end loop;
end Main;

output:

Base 2:  0.50000  0.25000  0.75000  0.12500  0.62500  0.37500  0.87500  0.06250  0.56250  0.31250
Base 3:  0.33333  0.66667  0.11111  0.44444  0.77778  0.22222  0.55556  0.88889  0.03704  0.37037
Base 4:  0.25000  0.50000  0.75000  0.06250  0.31250  0.56250  0.81250  0.12500  0.37500  0.62500
Base 5:  0.20000  0.40000  0.60000  0.80000  0.04000  0.24000  0.44000  0.64000  0.84000  0.08000

BBC BASIC

Works with: BBC BASIC for Windows

      @% = &20509
      FOR base% = 2 TO 5
        PRINT "Base " ; STR$(base%) ":"
        FOR number% = 0 TO 9
          PRINT FNvdc(number%, base%);
        NEXT
        PRINT
      NEXT
      END
 
      DEF FNvdc(n%, b%)
      LOCAL v, s%
      s% = 1
      WHILE n%
        s% *= b%
        v += (n% MOD b%) / s%
        n% DIV= b%
      ENDWHILE
      = v

Output:

Base 2:
  0.00000  0.50000  0.25000  0.75000  0.12500  0.62500  0.37500  0.87500  0.06250  0.56250
Base 3:
  0.00000  0.33333  0.66667  0.11111  0.44444  0.77778  0.22222  0.55556  0.88889  0.03704
Base 4:
  0.00000  0.25000  0.50000  0.75000  0.06250  0.31250  0.56250  0.81250  0.12500  0.37500
Base 5:
  0.00000  0.20000  0.40000  0.60000  0.80000  0.04000  0.24000  0.44000  0.64000  0.84000

bc

This solution hardcodes the literal 10 because numeric literals in bc can use any base from 2 to 16. This solution only works with integer bases from 2 to 16.

/*
 * Return the _n_th term of the van der Corput sequence.
 * Uses the current _ibase_.
 */
define v(n) {
	auto c, r, s
 
	s = scale
	scale = 0  /* to use integer division */
 
	/*
	 * c = count digits of n
	 * r = reverse the digits of n
	 */
	for (0; n != 0; n /= 10) {
		c += 1
		r = (10 * r) + (n % 10)
	}
 
	/* move radix point to left of digits */
	scale = length(r) + 6
	r /= 10 ^ c
 
	scale = s
	return r
}
 
t = 10
for (b = 2; b <= 4; b++) {
	"base "; b
	obase = b
	for (i = 0; i < 10; i++) {
		ibase = b
		"  "; v(i)
		ibase = t
	}
	obase = t
}
quit

Some of the calculations are not exact, because bc performs calculations using base 10. So the program prints a result like .202222221 (base 3) when the exact result would be .21 (base 3).

Output:

base 2
  0.00000000000000
  .10000000000000
  .01000000000000
  .11000000000000
  .00100000000000
  .10100000000000
  .01100000000000
  .11100000000000
  .00010000000000
  .10010000000000
base 3
  0.000000000
  .022222222
  .122222221
  .002222222
  .102222222
  .202222221
  .012222222
  .112222221
  .212222221
  .000222222
base 4
  0.0000000
  .1000000
  .2000000
  .3000000
  .0100000
  .1100000
  .2100000
  .310000000
  .0200000
  .1200000

C

#include <stdio.h>
 
void vc(int n, int base, int *num, int *denom)
{
        int p = 0, q = 1;
 
        while (n) {
                p = p * base + (n % base);
                q *= base;
                n /= base;
        }
 
        *num = p;  
        *denom = q;
 
        while (p) { n = p; p = q % p; q = n; }
        *num /= q;
        *denom /= q;
}
 
int main()
{
        int d, n, i, b;
        for (b = 2; b < 6; b++) {
                printf("base %d:", b);
                for (i = 0; i < 10; i++) {
                        vc(i, b, &n, &d);
                        if (n) printf("  %d/%d", n, d);
                        else   printf("  0");
                }
                printf("\n");
        }
 
        return 0;
}

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

C++

Translation of: Perl 6

#include <cmath>
#include <iostream>
 
double vdc(int n, double base = 2)
{
    double vdc = 0, denom = 1;
    while (n)
    {
        vdc += fmod(n, base) / (denom *= base);
        n /= base; // note: conversion from 'double' to 'int'
    }
    return vdc;
}
 
int main() 
{
    for (double base = 2; base < 6; ++base)
    {
        std::cout << "Base " << base << "\n";
        for (int n = 0; n < 10; ++n)
        {
            std::cout << vdc(n, base) << " ";
        }
        std::cout << "\n\n";
    }
}

Output:

Base 2
0 0.5 0.25 0.75 0.125 0.625 0.375 0.875 0.0625 0.5625 

Base 3
0 0.333333 0.666667 0.111111 0.444444 0.777778 0.222222 0.555556 0.888889 0.037037 

Base 4
0 0.25 0.5 0.75 0.0625 0.3125 0.5625 0.8125 0.125 0.375 

Base 5
0 0.2 0.4 0.6 0.8 0.04 0.24 0.44 0.64 0.84 

Common Lisp

(defun van-der-Corput (n base)
  (loop for d = 1 then (* d base) while (<= d n)
	finally
	(return (/ (parse-integer
		     (reverse (write-to-string n :base base))
		     :radix base)
		   d))))
 
(loop for base from 2 to 5 do
      (format t "Base ~a: ~{~6a~^~}~%" base
	      (loop for i to 10 collect (van-der-Corput i base))))

output

Base 2: 0     1/2   1/4   3/4   1/8   5/8   3/8   7/8   1/16  9/16  5/16  
Base 3: 0     1/3   2/3   1/9   4/9   7/9   2/9   5/9   8/9   1/27  10/27 
Base 4: 0     1/4   1/2   3/4   1/16  5/16  9/16  13/16 1/8   3/8   5/8   
Base 5: 0     1/5   2/5   3/5   4/5   1/25  6/25  11/25 16/25 21/25 2/25

D

import std.stdio, std.algorithm, std.range;
 
double vdc(int n, in double base=2.0) pure nothrow {
    double vdc = 0.0, denom = 1.0;
    while (n) {
        denom *= base;
        vdc += (n % base) / denom;
        n /= base;
    }
    return vdc;
}
 
void main() {
    foreach (b; 2 .. 6)
        writeln("\nBase ", b, ": ", iota(10).map!(n => vdc(n, b))());
}

Output:

Base 2: [0, 0.5, 0.25, 0.75, 0.125, 0.625, 0.375, 0.875, 0.0625, 0.5625]

Base 3: [0, 0.333333, 0.666667, 0.111111, 0.444444, 0.777778, 0.222222, 0.555556, 0.888889, 0.037037]

Base 4: [0, 0.25, 0.5, 0.75, 0.0625, 0.3125, 0.5625, 0.8125, 0.125, 0.375]

Base 5: [0, 0.2, 0.4, 0.6, 0.8, 0.04, 0.24, 0.44, 0.64, 0.84]

Ela

open random number list
 
vdc bs n = vdc' 0.0 1.0 n
  where vdc' v d n 
          | n > 0 = vdc' v' d' n'
          | else  = v
          where 
            d' = d * bs
            rem = n % bs
            n' = truncate (n / bs)
            v' = v + rem / d'

Test (with base 2.0, using non-strict map function on infinite list):

take 10 <| map' (vdc 2.0) [1..]

Output:

[0.5,0.25,0.75,0.125,0.625,0.375,0.875,0.0625,0.5625,0.3125]

Euphoria

Translation of: D

function vdc(integer n, atom base)
    atom vdc, denom, rem
    vdc = 0
    denom = 1
    while n do
        denom *= base
        rem = remainder(n,base)
        n = floor(n/base)
        vdc += rem / denom
    end while
    return vdc
end function
 
for i = 2 to 5 do
    printf(1,"Base %d\n",i)
    for j = 0 to 9 do
        printf(1,"%g ",vdc(j,i))
    end for
    puts(1,"\n\n")
end for

Output:

Base 2
0 0.5 0.25 0.75 0.125 0.625 0.375 0.875 0.0625 0.5625

Base 3
0 0.333333 0.666667 0.111111 0.444444 0.777778 0.222222 0.555556 0.888889 0.037037

Base 4
0 0.25 0.5 0.75 0.0625 0.3125 0.5625 0.8125 0.125 0.375

Base 5
0 0.2 0.4 0.6 0.8 0.04 0.24 0.44 0.64 0.84

F#

open System
 
let vdc n b =
    let rec loop n denom acc =
        if n > 0l then
            let m, remainder = Math.DivRem(n, b)
            loop m (denom * b) (acc + (float remainder) / (float (denom * b)))
        else acc
    loop n 1 0.0
 
 
[<EntryPoint>]
let main argv =
    printfn "%A" [ for n in 0 .. 9 -> (vdc n 2) ]
    printfn "%A" [ for n in 0 .. 9 -> (vdc n 5) ]
    0

Output

[0.0; 0.5; 0.25; 0.75; 0.125; 0.625; 0.375; 0.875; 0.0625; 0.5625]
[0.0; 0.2; 0.4; 0.6; 0.8; 0.04; 0.24; 0.44; 0.64; 0.84]

Forth

: fvdc ( base n -- f )
  0e 1e ( F: vdc denominator )
  begin dup while
    over s>d d>f f*
    over /mod  ( base rem n )
    swap s>d d>f fover f/
    frot f+ fswap
  repeat 2drop fdrop ;
 
: test  10 0 do 2 i fvdc cr f. loop ;

Output:

test
0.
0.5
0.25
0.75
0.125
0.625
0.375
0.875
0.0625
0.5625  ok

Go

package main
 
import "fmt"
 
func v2(n uint) (r float64) {
    p := .5
    for n > 0 {
        if n&1 == 1 {
            r += p
        }
        p *= .5
        n >>= 1
    }
    return
}
 
func newV(base uint) func(uint) float64 {
    invb := 1 / float64(base)
    return func(n uint) (r float64) {
        p := invb
        for n > 0 {
            r += p * float64(n%base)
            p *= invb
            n /= base
        }
        return
    }
}
 
func main() {
    fmt.Println("Base 2:")
    for i := uint(0); i < 10; i++ {
        fmt.Println(i, v2(i))
    }
    fmt.Println("Base 3:")
    v3 := newV(3)
    for i := uint(0); i < 10; i++ {
        fmt.Println(i, v3(i))
    }
}

Output:

Base 2:
0 0
1 0.5
2 0.25
3 0.75
4 0.125
5 0.625
6 0.375
7 0.875
8 0.0625
9 0.5625
Base 3:
0 0
1 0.3333333333333333
2 0.6666666666666666
3 0.1111111111111111
4 0.4444444444444444
5 0.7777777777777777
6 0.2222222222222222
7 0.5555555555555556
8 0.8888888888888888
9 0.037037037037037035

Haskell

The function vdc returns the n^th exact, arbitrary precision van der Corput number for any base ≥ 2 and any n. (A reasonable value is returned for negative values of n.)

import Data.List
import Data.Ratio
import System.Environment
import Text.Printf
 
-- A wrapper type for Rationals to make them look nicer when we print them.
newtype Rat = Rat Rational
instance Show Rat where
  show (Rat n) = show (numerator n) ++ "/" ++ show (denominator n)
 
-- Convert a list of base b digits to its corresponding number.  We assume the
-- digits are valid base b numbers and that their order is from least to most
-- significant.  
digitsToNum :: Integer -> [Integer] -> Integer
digitsToNum b = foldr1 (\d acc -> b * acc + d)
 
-- Convert a number to the list of its base b digits.  The order will be from
-- least to most significant.
numToDigits :: Integer -> Integer -> [Integer]
numToDigits _ 0 = [0]
numToDigits b n = unfoldr step n
  where step 0 = Nothing
        step m = let (q,r) = m `quotRem` b in Just (r,q)
 
-- Return the n'th element in the base b van der Corput sequence.  The base
-- must be ≥ 2.
vdc :: Integer -> Integer -> Rat
vdc b n | b < 2 = error "vdc: base must be ≥ 2"
        | otherwise = let ds = reverse $ numToDigits b n
                      in Rat (digitsToNum b ds % b ^ length ds)
 
-- Print the base followed by a sequence of van der Corput numbers.
printVdc :: (Integer,[Rat]) -> IO ()
printVdc (b,ns) = putStrLn $ printf "Base %d:" b 
                  ++ concatMap (printf " %5s" . show) ns
 
-- To print the n'th van der Corput numbers for n in [2,3,4,5] call the program 
-- with no arguments.  Otherwise, passing the base b, first n, next n and
-- maximum n will print the base b numbers for n in [firstN, nextN, ..., maxN].
main :: IO ()
main = do
  args <- getArgs
  let (bases, nums) = case args of
        [b, f, s, m] -> ([read b], [read f, read s..read m])
        _ -> ([2,3,4,5], [0..9])
  mapM_ printVdc [(b,rs) | b <- bases, let rs = map (vdc b) nums]

Output for small bases:

$ ./vandercorput 
Base 2:   0/1   1/2   1/4   3/4   1/8   5/8   3/8   7/8  1/16  9/16
Base 3:   0/1   1/3   2/3   1/9   4/9   7/9   2/9   5/9   8/9  1/27
Base 4:   0/1   1/4   1/2   3/4  1/16  5/16  9/16 13/16   1/8   3/8
Base 5:   0/1   1/5   2/5   3/5   4/5  1/25  6/25 11/25 16/25 21/25

Output for a larger base. (Base 123 for n ∈ [50, 100, …, 300].)

$ ./vandercorput 123 50 100 300
Base 123: 50/123 100/123 3322/15129 9472/15129 494/15129 6644/15129

Icon and Unicon

The following solution works in both Icon and Unicon:

procedure main(A)
    base := integer(get(A)) | 2
    every writes(round(vdc(0 to 9,base),10)," ")
    write()
end
 
procedure vdc(n, base)
    e := 1.0
    x := 0.0
    while x +:= 1(((0 < n) % base) / (e *:= base), n /:= base)
    return x
end
 
procedure round(n,d)
    places := 10 ^ d
    return real(integer(n*places + 0.5)) / places
end

and a sample run is:

->vdc
0.0 0.5 0.25 0.75 0.125 0.625 0.375 0.875 0.0625 0.5625 
->vdc 3
0.0 0.3333333333 0.6666666667 0.1111111111 0.4444444444 0.7777777778 0.2222222222 0.5555555556 0.8888888889 0.037037037 
->vdc 5
0.0 0.2 0.4 0.6 0.8 0.04 0.24 0.44 0.64 0.84 
->vdc 123
0.0 0.0081300813 0.0162601626 0.0243902439 0.0325203252 0.0406504065 0.0487804878 0.0569105691 0.0650406504 0.07317073170000001 
->

An alternate, Unicon-specific implementation of vdc patterned after the functional Perl 6 solution is:

procedure vdc(n, base)
    s1 := create |((0 < 1(.n, n /:= base)) % base)
    s2 := create 2(e := 1.0, |(e *:= base))
    every (result := 0) +:= |s1() / s2()
    return result
end

It produces the same output as shown above.

J

Solution:

vdc=: ([ %~ %@[ #. #.inv)"0 _

Examples:

   2 vdc i.10                NB. 1st 10 nums of Van der Corput sequence in base 2
0 0.5 0.25 0.75 0.125 0.625 0.375 0.875 0.0625 0.5625
   2x vdc i.10               NB. as above but using rational nums
0 1r2 1r4 3r4 1r8 5r8 3r8 7r8 1r16 9r16
   2 3 4 5x vdc i.10         NB. 1st 10 nums of Van der Corput sequence in bases 2 3 4 5
0 1r2 1r4 3r4  1r8  5r8  3r8   7r8  1r16  9r16
0 1r3 2r3 1r9  4r9  7r9  2r9   5r9   8r9  1r27
0 1r4 1r2 3r4 1r16 5r16 9r16 13r16   1r8   3r8
0 1r5 2r5 3r5  4r5 1r25 6r25 11r25 16r25 21r25

In other words: use the left argument as the "base" to structure the sequence numbers into digits. Then use the reciprocal of the left argument as the "base" to re-represent this sequence and divide that result by the left argument to get the Van der Corput sequence number.

Java

Translation of: Perl 6

Using (denom *= 2) as the denominator is not a recommended way of doing things since it is not clear when the multiplication and assignment happen. Comparing this to the "++" operator, it looks like it should do the doubling and assignment second. Comparing it to the "++" operator used as a preincrement operator, it looks like it should do the doubling and assignment first. Comparing it to the behavior of parentheses, it looks like it should do the doubling and assignment first. Luckily for us, it works the same in Java as in Perl 6 (doubling and assignment first). It was kept the Perl 6 way to help with the comparison. Normally, we would initialize denom to 2 (since that is the denominator of the leftmost digit), use it alone in the vdc sum, and then double it after.

public class VanDerCorput{
	public static double vdc(int n){
		double vdc = 0;
		int denom = 1;
		while(n != 0){
			vdc += n % 2.0 / (denom *= 2);
			n /= 2;
		}
		return vdc;
	}
 
	public static void main(String[] args){
		for(int i = 0; i <= 10; i++){
			System.out.println(vdc(i));
		}
	}
}

Output:

0.0
0.5
0.25
0.75
0.125
0.625
0.375
0.875
0.0625
0.5625
0.3125

Mathematica

VanDerCorput[n_,base_:2]:=Table[
  FromDigits[{Reverse[IntegerDigits[k,base]],0},base],
{k,n}]

VanDerCorput[10,2]
->{1/2,1/4,3/4,1/8,5/8,3/8,7/8,1/16,9/16,5/16}

VanDerCorput[10,3]
->{1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9, 1/27, 10/27}

VanDerCorput[10,4]
->{1/4, 1/2, 3/4, 1/16, 5/16, 9/16, 13/16, 1/8, 3/8, 5/8}

VanDerCorput[10,5]
->{1/5, 2/5, 3/5, 4/5, 1/25, 6/25, 11/25, 16/25, 21/25, 2/25}

MATLAB / Octave

    function x = corput (n)
    b = dec2bin(1:n)-'0';   % generate sequence of binary numbers from 1 to n
    l = size(b,2);          % get number of binary digits 
    w = (1:l)-l-1;          % 2.^w are the weights
    x = b * ( 2.^w');       % matrix times vector multiplication for 
    end;  

Output:

 corput(10)
 ans =

   0.500000
   0.250000
   0.750000
   0.125000
   0.625000
   0.375000
   0.875000
   0.062500
   0.562500
   0.312500

PARI/GP

VdC(n)=n=binary(n);sum(i=1,#n,if(n[i],1.>>(#n+1-i)));
VdC(n)=sum(i=1,#binary(n),if(bittest(n,i-1),1.>>i)); \\ Alternate approach
vector(10,n,VdC(n))

Output:

[0.500000000, 0.250000000, 0.750000000, 0.125000000, 0.625000000, 0.375000000, 0.875000000, 0.0625000000, 0.562500000, 0.312500000]

Perl

Translation of: Perl6

sub vdc {
    my @value = shift;
    my $base = shift // 2;
    use integer;
    push @value, $value[-1] / $base while $value[-1] > 0;
    my ($x, $sum) = (1, 0);
    no integer;
    $sum += ($_ % $base) / ($x *= $base) for @value;
    return $sum;
}
 
for my $base ( 2 .. 5 ) {
    print "base $base: ", join ' ', map { vdc($_, $base) } 0 .. 10;
    print "\n";
}

Perl 6

First we present 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) for ^10).perl;
    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 @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 Perl 6 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 Perl 6 distinguishes "sentences" from "noun phrases" as a natural language might.

PicoLisp

(scl 6)
 
(de vdc (N B)
   (default B 2)
   (let (R 0  A 1.0)
      (until (=0 N)
         (inc 'R (* (setq A (/ A B)) (% N B)))
         (setq N (/ N B)) )
      R ) )
 
(for B (2 3 4)
   (prinl "Base: " B)
   (for N (range 0 9)
      (prinl N ": " (round (vdc N B) 4)) ) )

Output:

Base: 2
0: 0.0000
1: 0.5000
2: 0.2500
3: 0.7500
4: 0.1250
5: 0.6250
6: 0.3750
7: 0.8750
8: 0.0625
9: 0.5625
Base: 3
0: 0.0000
1: 0.3333
2: 0.6667
3: 0.1111
4: 0.4444
5: 0.7778
6: 0.2222
7: 0.5556
8: 0.8889
9: 0.0370
Base: 4
0: 0.0000
1: 0.2500
2: 0.5000
3: 0.7500
4: 0.0625
5: 0.3125
6: 0.5625
7: 0.8125
8: 0.1250
9: 0.3750

PL/I

 
vdcb: procedure (an) returns (bit (31)); /* 6 July 2012 */
   declare an fixed binary (31);
   declare (n, i) fixed binary (31);
   declare v bit (31) varying;
 
   n = an; v = ''b;
   do i = 1 by 1 while (n > 0);
      if iand(n, 1) = 1 then v = v || '1'b; else v = v || '0'b;
      n = isrl(n, 1);
   end;
   return (v);
end vdcb;
 
   declare i fixed binary (31);
 
   do i = 0 to 10;
      put skip list ('0.' || vdcb(i));
   end;
 

Output:

0.0000000000000000000000000000000 
0.1000000000000000000000000000000 
0.0100000000000000000000000000000 
0.1100000000000000000000000000000 
0.0010000000000000000000000000000 
0.1010000000000000000000000000000 
0.0110000000000000000000000000000 
0.1110000000000000000000000000000 
0.0001000000000000000000000000000 
0.1001000000000000000000000000000 
0.0101000000000000000000000000000 

Prolog

% vdc( N, Base, Out )
% Out = the Van der Corput representation of N in given Base
vdc( 0, _, [] ).
vdc( N, Base, Out ) :-
    Nr is mod(N, Base),
    Nq is N // Base,
    vdc( Nq, Base, Tmp ),
    Out = [Nr|Tmp].
 
% Writes every element of a list to stdout; no newlines
write_list( [] ).
write_list( [H|T] ) :-
    write( H ),
    write_list( T ).
 
% Writes the Nth Van der Corput item.
print_vdc( N, Base ) :-
    vdc( N, Base, Lst ),
    write('0.'),
    write_list( Lst ).
print_vdc( N ) :-
    print_vdc( N, 2 ).
 
% Prints the first N+1 elements of the Van der Corput
% sequence, each to its own line
print_some( 0, _ ) :-
    write( '0.0' ).
print_some( N, Base ) :-
    M is N - 1,
    print_some( M, Base ),
    nl,
    print_vdc( N, Base ).
print_some( N ) :-
    print_some( N, 2 ).
 
test :-
   writeln('First 10 members in base 2:'),
   print_some( 9 ),
   nl,
   write('7th member in base 4 (stretch goal) => '),
   print_vdc( 7, 4 ).
 

Output (result of test):

First 10 members in base 2:
0.0
0.1
0.01
0.11
0.001
0.101
0.011
0.111
0.0001
0.1001
7th member in base 4 (stretch goal) => 0.31
true .

Python

(Python3.x)

The multi-base sequence generator

def vdc(n, base=2):
    vdc, denom = 0,1
    while n:
        denom *= base
        n, remainder = divmod(n, base)
        vdc += remainder / denom
    return vdc

Sample output

Base 2 and then 3:

>>> [vdc(i) for i in range(10)]
[0, 0.5, 0.25, 0.75, 0.125, 0.625, 0.375, 0.875, 0.0625, 0.5625]
>>> [vdc(i, 3) for i in range(10)]
[0, 0.3333333333333333, 0.6666666666666666, 0.1111111111111111, 0.4444444444444444, 0.7777777777777777, 0.2222222222222222, 0.5555555555555556, 0.8888888888888888, 0.037037037037037035]
>>> 

As fractions

We can get the output as rational numbers if we use the fraction module (and change its string representation to look like a fraction):

>>> from fractions import Fraction
>>> Fraction.__repr__ = lambda x: '%i/%i' % (x.numerator, x.denominator)
>>> [vdc(i, base=Fraction(2)) for i in range(10)]
[0, 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16]

Stretch goal

Sequences for different bases:

>>> for b in range(3,6):
	print('\nBase', b)
	print([vdc(i, base=Fraction(b)) for i in range(10)])
 
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]

Racket

Following the suggestion.

#lang racket
(define (van-der-Corput n base)
  (if (zero? n)
      0
      (let-values ([(q r) (quotient/remainder n base)])
        (/ (+ r (van-der-Corput q base))
           base))))

By digits, extracted arithmetically.

#lang racket
(define (digit-length n base)
  (if (< n base) 1 (add1 (digit-length (quotient n base) base))))
(define (digit n i base)
  (remainder (quotient n (expt base i)) base))
(define (van-der-Corput n base)
  (for/sum ([i (digit-length n base)]) (/ (digit n i base) (expt base (+ i 1)))))

Output.

(for ([base (in-range 2 (add1 5))])
  (printf "Base ~a: " base)
  (for ([n (in-range 0 10)])
    (printf "~a " (van-der-Corput n base)))
  (newline))
 
#| 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 |# 

REXX

binary version

This version only handles binary (base 2).
Virtually any integer (including negative) is allowed and is accurate (no rounding).
A range of integers is also supported.

/*REXX pgm converts any integer (or a range) to a van der Corput number in base 2*/
/*convert any integer (or a range) to a van der Corput number in  base 2*/
 
numeric digits 1000                    /*handle anything the user wants.*/
parse arg a b .                        /*obtain the number(s)  [maybe]. */
if a=='' then do;  a=0;  b=10;  end    /*if none specified, use defaults*/
if b=='' then b=a                      /*assume a "range" of a single #.*/
 
      do j=a to b                      /*traipse through the range.     */
      _=vdC(abs(j))                    /*convert abs value of integer.  */
      leading=substr('-',2+sign(j))    /*if needed, leading minus sign. */
      say leading || _                 /*show number (with leading -  ?)*/
      end   /*j*/
exit                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────VDC [van der Corput] subroutine─────*/
vdC: procedure;  y=x2b(d2x(arg(1)))    /*convert to  hex,  then binary. */
if y=0 then return 0                   /*zero has been converted to 0000*/
       else return '.'reverse(strip(y,"L",0))    /*heavy lifting by REXX*/

output when using the input of: 0 10

0
.1
.01
.11
.001
.101
.011
.111
.0001
.1001
.0101

any radix up to 90

This version handles what the first version does, plus any radix up to base 90.
It can also support a list (enabled when the base is negative).

/*REXX pgm converts any integer (or a range) to a van der Corput number in base 2,*/
/*                  or optionaly, any other base up to base 90.         */
/*If the base is negative, the output is shown as a list.               */
 
numeric digits 1000                    /*handle anything the user wants.*/
parse arg a b r .                      /*obtain the number(s)  [maybe]. */
if a=='' then do;  a=0;  b=10;  end    /*if none specified, use defaults*/
if b=='' then b=a                      /*assume a "range" of a single #.*/
if r=='' then r=2                      /*assume a radix (base) of  2.   */
z=                                     /*placeholder for a list of nums.*/
 
      do j=a to b                      /*traipse through the range.     */
      _=vdC(abs(j),abs(r))             /*convert abs value of integer.  */
      _=substr('-',2+sign(j))_         /*if needed, leading minus sign. */
      if r>0 then say _                /*if positive base, just show it.*/
             else z=z _                /*        ... else build a list. */
      end   /*j*/
 
if z\=='' then say strip(z)            /*if list wanted, then show it.  */
exit                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────VDC [van der Corput] subroutine─────*/
vdC: return '.'reverse(base(arg(1),arg(2)))  /*convert, reverse, append.*/
/*──────────────────────────────────BASE subroutine (up to base 90)─────*/
base: procedure; parse arg x,toB,inB   /*get a number,  toBase,  inBase */
 
/*┌────────────────────────────────────────────────────────────────────┐
┌─┘ Input to this subroutine    (all must be positive whole numbers):  └─┐
│                                                                        │
│                          x       (is required).                        │
│                        toBase    the base to convert   X   to.         │
│                        inBase    the base  X  is expressed in.         │
│                                                                        │
│   toBase  or  inBase    can be omitted   which causes the default of   │
└─┐        10  to be used.   The limits of both are:    2 ──► 90.      ┌─┘
  └────────────────────────────────────────────────────────────────────┘*/
 
@abc='abcdefghijklmnopqrstuvwxyz'      /*random characters, sorted.     */
@abcU=@abc; upper @abcU                /*go whole hog and extend 'em.   */
@@@=0123456789||@abc||@abcU            /*prefix 'em with numeric digits.*/
@@@=@@@'<>[]{}()?~!@#$%^&*_+-=|\/;:~'  /*add some special chars as well.*/
                                       /*spec. chars should be viewable.*/
numeric digits 1000                    /*what the hey, support biggies. */
maxB=length(@@@)                       /*max base (radix) supported here*/
parse arg x,toB,inB                    /*get a number, toBase, inBase   */
if toB=='' then toB=10                 /*if skipped, assume default (10)*/
if inB=='' then inB=10                 /* "    "        "      "      " */
 
/*══════════════════════════════════convert X from base inB ──► base 10.*/
#=0
      do j=1 for length(x)
      _=substr(x,j,1)                  /*pick off a "digit" from X.     */
      v=pos(_,@@@)                     /*get the value of this "digits".*/
      if v==0 |v>inB then call erd x,j,inB           /*illegal "digit"? */
      #=#*inB+v-1                      /*construct new num, dig by dig. */
      end   /*j*/
 
/*══════════════════════════════════convert # from base 10 ──► base toB.*/
y=
        do while #>=toB                /*deconstruct the new number (#).*/
        y=substr(@@@,(#//toB)+1,1)y    /*construnct the output number.  */
        #=#%toB                        /*... and whittle  #  down also. */
        end   /*while*/
 
return substr(@@@,#+1,1)y

output when using the multiple inputs of (where a negative base indicates to show numbers as a list):

0 30 -2
1 30 -3
1 30 -4
1 30 -5
55582777 55582804 -80

(All outputs are a single line list.)

.0 .1 .01 .11 .001 .101 .011 .111 .0001 .1001 .0101 .1101 .0011 .1011 .0111 .1111 .00001 .10001 .01001 .11001 .00101 .10101 .01101 .11101 .00011 .10011 .01011 .11011 .00111 .10111 .01111
.1 .2 .01 .11 .21 .02 .12 .22 .001 .101 .201 .011 .111 .211 .021 .121 .221 .002 .102 .202 .012 .112 .212 .022 .122 .222 .0001 .1001 .2001 .0101
.1 .2 .3 .01 .11 .21 .31 .02 .12 .22 .32 .03 .13 .23 .33 .001 .101 .201 .301 .011 .111 .211 .311 .021 .121 .221 .321 .031 .131 .231
.1 .2 .3 .4 .01 .11 .21 .31 .41 .02 .12 .22 .32 .42 .03 .13 .23 .33 .43 .04 .14 .24 .34 .44 .001 .101 .201 .301 .401 .011
.V[Is1 .W[Is1 .X[Is1 .Y[Is1 .Z[Is1 .<[Is1 .>[Is1 .[[Is1 .][Is1 .{[Is1 .}[Is1 .([Is1 .)[Is1 .?[Is1 .~[Is1 .![Is1 .@[Is1 .#[Is1 .$[Is1 .%[Is1 .^[Is1 .&[Is1 .*[Is1 .0]Is1 .1]Is1 .2]Is1 .3]Is1 .4]Is1

Ruby

The multi-base sequence generator

def vdc(n, base=2)
  str = n.to_s(base).reverse
  str.to_i(base).quo(base ** str.length)
end

Sample output

Base 3

> Array.new(10){|i| vdc(i,3)}
=> [Rational(0, 1), Rational(1, 3), Rational(2, 3), Rational(1, 9), Rational(4, 9), Rational(7, 9), Rational(2, 9), Rational(5, 9), Rational(8, 9), Rational(1, 27)]

Seed7

Translation of: D

$ include "seed7_05.s7i";
  include "float.s7i";
 
const func float: vdc (in var integer: number, in integer: base) is func
  result
    var float: vdc is 0.0;
  local
    var integer: denom is 1;
    var integer: remainder is 0;
  begin
    while number <> 0 do
      denom *:= base;
      remainder := number rem base;
      number := number div base;
      vdc +:= flt(remainder) / flt(denom);
    end while;
  end func;
 
const proc: main is func
  local
    var integer: base is 0;
    var integer: number is 0;
  begin
    for base range 2 to 5 do
      writeln;
      writeln("Base " <& base);
      for number range 0 to 9 do
        write(vdc(number, base) digits 6 <& " ");
      end for;
      writeln;
    end for;
  end func;

Output:

Base 2
0.000000 0.500000 0.250000 0.750000 0.125000 0.625000 0.375000 0.875000 0.062500 0.562500 

Base 3
0.000000 0.333333 0.666667 0.111111 0.444444 0.777778 0.222222 0.555556 0.888889 0.037037 

Base 4
0.000000 0.250000 0.500000 0.750000 0.062500 0.312500 0.562500 0.812500 0.125000 0.375000 

Base 5
0.000000 0.200000 0.400000 0.600000 0.800000 0.040000 0.240000 0.440000 0.640000 0.840000 

Tcl

The core of this is code to handle digit reversing. Note that this also tackles negative numbers (by preserving the sign independently).

proc digitReverse {n {base 2}} {
    set n [expr {[set neg [expr {$n < 0}]] ? -$n : $n}]
    set result 0.0
    set bit [expr {1.0 / $base}]
    for {} {$n > 0} {set n [expr {$n / $base}]} {
	set result [expr {$result + $bit * ($n % $base)}]
	set bit [expr {$bit / $base}]
    }
    return [expr {$neg ? -$result : $result}]
}

Note that the above procedure will produce terms of the Van der Corput sequence by default.

# Print the first 10 terms of the Van der Corput sequence
for {set i 1} {$i <= 10} {incr i} {
    puts "vanDerCorput($i) = [digitReverse $i]"
}
 
# In other bases
foreach base {3 4 5} {
    set seq {}
    for {set i 1} {$i <= 10} {incr i} {
	lappend seq [format %.5f [digitReverse $i $base]]
    }
    puts "${base}: [join $seq {, }]"
}

Output:

vanDerCorput(1) = 0.5
vanDerCorput(2) = 0.25
vanDerCorput(3) = 0.75
vanDerCorput(4) = 0.125
vanDerCorput(5) = 0.625
vanDerCorput(6) = 0.375
vanDerCorput(7) = 0.875
vanDerCorput(8) = 0.0625
vanDerCorput(9) = 0.5625
vanDerCorput(10) = 0.3125
3: 0.33333, 0.66667, 0.11111, 0.44444, 0.77778, 0.22222, 0.55556, 0.88889, 0.03704, 0.37037
4: 0.25000, 0.50000, 0.75000, 0.06250, 0.31250, 0.56250, 0.81250, 0.12500, 0.37500, 0.62500
5: 0.20000, 0.40000, 0.60000, 0.80000, 0.04000, 0.24000, 0.44000, 0.64000, 0.84000, 0.08000

XPL0

include c:\cxpl\codes;  \intrinsic 'code' declarations
 
func real VdC(N);       \Return Nth term of van der Corput sequence in base 2
int  N;
real V, U;
[V:= 0.0;  U:= 0.5;
repeat  N:= N/2;
        if rem(0) then V:= V+U;
        U:= U/2.0;
until   N=0;
return V;
];
 
int N;
for N:= 0 to 10-1 do
        [IntOut(0, N);  RlOut(0, VdC(N));  CrLf(0)]

Output:

0    0.00000
1    0.50000
2    0.25000
3    0.75000
4    0.12500
5    0.62500
6    0.37500
7    0.87500
8    0.06250
9    0.56250