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




2

0




{\displaystyle 2^{0}}

; the digit in the next column to the left has a multiplier of 




2

1




{\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 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 2^{-1}}

, or 



1

/

2


{\displaystyle 1/2}

.
The weight for the second column to the right of the point is 




2

−
2




{\displaystyle 2^{-2}}

 or 



1

/

4


{\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 0\times 2^{-1}+1\times 2^{-2}}

 or 



1

/

4


{\displaystyle 1/4}

.



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




0
≤
x
<
1


{\displaystyle 0\leq x<1}


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 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 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


*        Van der Corput sequence   31/01/2017
VDCS     CSECT
         USING  VDCS,R13           base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         " <-
         ST     R15,8(R13)         " ->
         LR     R13,R15            " addressability
         ZAP    B,=P'2'            b=2  (base)
         ZAP    M,=P'-1'           m=-1
         SR     R6,R6              i=0
LOOPI    CH     R6,=H'10'          do i=0 to 10
         BH     ELOOPI
         AP     M,=P'1'            w=m+1
         ZAP    V,=P'0'            v=0
         ZAP    S,=P'1'            s=1
         ZAP    N,M                n=m
WHILE    CP     N,=P'0'            do while n<>0
         BE     EWHILE
         MP     S,B                s=s*b
         ZAP    PL16,N             n
         DP     PL16,B             n/b
         ZAP    W,PL16+8(8)        w=n mod b 
         MP     W,=P'100000'       *100000
         ZAP    PL16,W             w
         DP     PL16,S             w/s
         ZAP    W,PL16(8)          w=w/s
         AP     V,W                v=v+(n mod b)*100000/s
         ZAP    PL16,N             n
         DP     PL16,B             n/b
         ZAP    N,PL16(8)          n=n/b
         B      WHILE
EWHILE   XDECO  R6,XDEC            edit i
         MVC    PG+0(3),XDEC+9     output i
         MVC    PG+3(3),=C' 0.'
         UNPK   Z,V                unpack v
         OI     Z+L'Z-1,X'F0'      edit v
         MVC    PG+6(5),Z+11       output v  (v/100000)
         XPRNT  PG,L'PG            print buffer
         LA     R6,1(R6)           i=i+1
         B      LOOPI
ELOOPI   L      R13,4(0,R13)       epilog 
         LM     R14,R12,12(R13)    " restore
         XR     R15,R15            " rc=0
         BR     R14                exit
B        DS     PL8
M        DS     PL8
V        DS     PL8
S        DS     PL8
N        DS     PL8
W        DS     PL8                packed 
Z        DS     ZL16               zoned
PL16     DS     PL16               packed max
PG       DC     CL80' '            buffer
XDEC     DS     CL12               work area for xdeco
         YREGS
         END    VDCS