Convert the Binary Champernowne Constant to Decimal

Question

The Champernowne constant is a transcendental decimal number whose digits are the concatination of all positive integers.

C₁₀ = 0.12345678910111213141516...₁₀

The binary version of this is

C₂ = 0.1101110010111011110001...₂

Write a program that prints C₂ in decimal. The program should never halt. It should continue printing digits such that given infinite time and memory, it will print an infinite number of correct digits.

To illustrate this, you must account for integer overflow, since integer overflow will either cause an error or print incorrect digits, even with infinite memory available.

To test your code, here are the first 150 digits of this number.

0.862240125868054571557790283249394578565764742768299094516071214557306740590516458042038441438618133400466718933678923129464456214392016383510596824661

Shortest code wins.

Answer 1

Python 119 bytes

import sys
r=i=n=0
while 1:
 i+=1
 for b in bin(i)[2:]:n+=1;r=r*10+int(b)*5**n;~n%4or sys.stdout.write(('0.'+`r`)[n/4])

Given unlimited memory, this will run indefinitely, although it does slow down quite a bit after the first few thousand digits.

Each binary bit is treated as its corresponding power of 5, i.e:
0.1 ⇒ 5, 0.01 ⇒ 25, 0.001 ⇒ 125, 0.0001 ⇒ 625, etc.

Which lends itself nicely to a decimal conversion, as:
1/2 = 0.5, 1/4 = 0.25, 1/8 = 0.125, 1/16 = 0.0625, etc.

The variable r stores a running total of all bits so far (increasing by a factor of 10 each iteration), and every four bits the next digit is output. This is mathematically correct, because

log2(10) ≈ 3.321928

which means that every 3.32 or so binary bits will produce one decimal digit. 10/3 is a better upper bound, but I chose 4 for sake of brevity.

Ruby 80 bytes

r=i=n=0
$><<gsub(/./){"0.#{r=r*10+$&.to_i*5**n+=1}"[n/4,n%4/3]}while$_='%b'%i+=1

Same algorithm as above. It's been a while since I've golfed Ruby, so I may be missing a few tricks.

GolfScript 53 bytes

0:µ.{).2base{5µ):µ?*@10*+.'0.'\+µ4/<µ(4/>print\}/.}do

Once again, same algorithm. This is one of the first things I've ever written in GolfScript, so I'm fairly certain that it can be reduced further. I've chosen to use µ (char 181) as a variable name, because it saves a whitespace in the expression µ4/.

Answer 2

Mathematica 73 65 85

Edit:

s = {}; n = 1; While[n < 50, s = Join[s, IntegerDigits[n, 2]]; 
Print[N[FromDigits[{s, 0}, 2], n]]; n++]

Explanation:

s holds the base-2 digits of 1, 2, 3,...n, as a list of digits, {1,1,0,1,1,1,0,0,...}. Then FromDigits inserts the decimal point (with the 2 indicating the position), treating the input as a base-2 decimal and generating a base-10 decimal as output.

---

Using the built-in function: 51 chars

n=1;While[True,Print@N[ChampernowneNumber@2,n];n++]

Answer 3

Python, 225

import sys,fractions
w=sys.stdout.write
w('0.')
h=t=10
l=n=0
p=fractions.Fraction(5)
i=int
while 1:
 while i(h)!=i(l):
  n+=1
  for c in bin(n)[2:]:
    if c=='1':l+=p
    else:h-=p
    p/=2
 w(str(i(h)));h-=i(h);l-=i(l);h*=t;l*=t;p*=t

Note that the 4-space indentation should be tab characters. They seem to be converted to spaces when displayed here.

Explanation

h and l are the highest and lowest possible values for the current digit, as fractions.

For example, if h is 7/2 or 3.5, the current digit is at most 3, and if it is 3, then the next digit is at most 5.

When int(h) == int(l), we know what the next digit is, so we print that, subtract it from h and l, and multiply them by 10 to get the bounds for the next digit.

When int(h) != int(l), we improve our bounds by looking further into C₂. For the nth decimal place in the output and bth binary place in C₂, a 1 means l increases by 10^n/2^b and a 0 means h decreases by that amount.

Answer 4

GolfScript, 71 characters

1.0.){:q,{\.+)q*+\.+q*\.)3$*2$/1$4$*3$/:&-!{&10%print@10*@@}*}/q.+s}:s~

Maybe not the best puzzle for GolfScript but tried a solution anyways. The code does iterates infinitely due to an unlimited recursion and prints the digits one after the next (one of the rare cases where the print built-in is needed).

Note that the online version has a cutoff for the recursion.