Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

C10 = 0.12345678910111213141516...10

The binary version of this is

C2 = 0.1101110010111011110001...2

Write a program that prints C2 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.

share|improve this question
1  
the last digit of C_2 is wrong. should be removed or changed to 1 –  ardnew Dec 14 '12 at 18:09
    
Thanks, it's fixed now. –  cardboard_box Dec 14 '12 at 18:42

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
    
I'm eventually going to just give up any time I see an answer by primo. I can't win. –  jdstankosky Dec 19 '12 at 18:26
    
I've participated in several different code golfing sites/fora, typically with automated scoring. The major drawback is that you can't share your solution with anyone. I was a bit hesitant at first, but I've come to enjoy the Q&A format, particularly because you can share with everyone. I might be a bit long-winded regarding implementation details, but this is exactly what I like to see in other posts. I routinely vote up other solutions in the same thread, if they make me think about the problem in a new way. If I thought I were discouraging other users from posting, I would stop. –  primo Dec 19 '12 at 18:54
    
Not at all, I'm learning a lot from your answers. My comment was meant to be humorous and praising. You always approach the questions in ways I might never have considered. TBH, I actually look for your answers because I know they'll be great resources, and kind of get crestfallen when I can't find them. I'm still trying to work out your Pokemon solution in PHP, for example. As a PHP hobbyist turning pro, I find your "long-winded" explanations invaluable. –  jdstankosky Dec 19 '12 at 19:02
    
I've received similar comments from users who weren't kidding (although not here (yet)), so I wasn't sure. If you're an IRC user, might I suggest #phpgolf on the FreeNode network. I think you'll find you're in good company. –  primo Dec 19 '12 at 19:18

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++]
share|improve this answer

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 C2. For the nth decimal place in the output and bth binary place in C2, a 1 means l increases by 10^n/2^b and a 0 means h decreases by that amount.

share|improve this answer

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.

share|improve this answer
    
Nice solution, but it seems to be missing a decimal point. –  cardboard_box Dec 14 '12 at 18:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.