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.

Khinchin's constant is a curious mathematical constant that, according to Wolfram MathWold, is "notoriously difficult to calculate to high precision".

Here it is to 100 digits:

2.685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697...

Write a program in 64 bytes or less that outputs Khinchin's constant to the maximum number of correct decimal places. (Note that it is no longer 32 bytes.)

  • You may not use any built in library constants or functions directly relating to Khinchin's constant. (e.g. Math.Khinchin(precision) is definitely not allowed.)
  • You may use math libraries to compute logarithms, summations, etc.
  • You may hardcode all or part of your answer.
  • Your program must produce finite output and run in less than an hour on a reasonably modern computer (such as those listed here).
  • You must output to stdout. There is no input.
  • You may use any characters you want as long as http://mothereff.in/byte-counter registers 64 bytes or less.

Scoring

Your score is the number of successive digits in Khinchin's constant your program outputs correctly, starting with 2.68... You may output incorrect digits but only the last correct digit is counted towards your score.

For example, an output of

2.68545200206530644530971483548179569382038229399446295305115234555721

would score 9 points. One for each of the digits 2 6 8 5 4 5 2 0 0 but nothing after the 2 that should be a 1.

share|improve this question
2  
Why are you allowing hardcoding the entire answer? –  William Barbosa Jul 18 at 18:07
3  
@WilliamBarbosa why not? ideally there should be a solution that scores better than 31. if not, well that's unfortunate. –  Martin Büttner Jul 18 at 18:11
1  
Is unicode allowed? How to count it? –  aditsu Jul 18 at 18:42
2  
You should allow 64b instead of 32, and count all chars as UTF-8 bytes (mothereff.in/byte-counter) (=1 to 4 bytes per char depending on the Unicode plane). Also, the existing solutions could easily be adapted to 64b –  xem Jul 18 at 19:57
2  
@PeterTaylor I coded a CJam floating-point solution, and let me tell you, limited precision is not the main problem :p –  aditsu Jul 18 at 20:06

13 Answers 13

up vote 8 down vote accepted

Maple, 200+

The following Maple command computes Khinchin's constant to the requested precision (here, 200 digits):

evalf[200](exp(sum((-1)^k*(2-2^k)*ζ(1,k)/k,k=2..∞)/ln(2)));

This code should work if you copy-paste it into the Maple graphical interface. The ζ takes two bytes in UTF-8, and the three, for a total of 62 bytes.

Writing out the ASCII versions of those symbols, even with the trick of using min() instead of infinity, alas, brings the byte count up to 66:

evalf[200](exp(sum((-1)^k*(2-2^k)*Zeta(1,k)/k,k=2..min())/ln(2)));

The number of digits computed can be easily adjusted by changing the number in square brackets after evalf. On my rather old computer, 200 digits seems to finish in about half an hour; yours might be capable of more. Note that Maple rounds the result to the requested precision instead of truncating it, so the actual number of matching digits might be somewhat less.

This method of calculating the constant is based on formula (9) from the MathWorld page, cited there to Gosper (1996, pers. comm.):

            Equation

This was the most efficient method that I managed to (barely) squeeze into 64 bytes or less.

share|improve this answer
    
Pretty neat. If only I had Maple :/ –  Calvin's Hobbies Jul 20 at 9:40

CJam - 118

2'."*;TeT?_aN{.i9B*ZEay
G`9~eW}nE=Lr-`B}    )D>9m9"136b

Try it at http://cjam.aditsu.net/

Since stackexchange destroys some of the characters, here's a program that generates the program above; run it first, then run its output:

"2'.\""685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697995153465905288090 136b:c"\"136b"

Explanation:

2 pushes 2
'. pushes the dot
"…" is a string containing the rest of the digits in encoded form
128b converts the string to a number, treating the characters as digits in base 128 (via their ASCII code)

share|improve this answer
2  
Very nice. Can you explain it a bit? –  Kyle Kanos Jul 18 at 19:01
    
@KyleKanos added explanation –  aditsu Jul 18 at 19:07
    
That's awesome. I should learn CJam one day... Also, I cannot get your online interpreter to work in Opera web browser, though it works on my Firefox. Probably an Opera-issue, but thought I'd mention it. –  Kyle Kanos Jul 18 at 19:12
1  
@Calvin'sHobbies In 1997 Xavier Gourdon computed the first 110,000 digits in 22 hours using at most a 250MHz processor. So you might be able to compute 1000 times as many digits as this solution in an hour. web.archive.org/web/20120218093629/http://pi.lacim.uqam.ca/… –  Alex L Jul 20 at 10:54
1  
@Calvin'sHobbies see this link for a complete program that reportedly calculated 2000 digits in 7 seconds. –  aditsu Jul 20 at 12:31

Kona 63

Simple hard-coded answer:

2.68545200106530644530971483548179569382038229399446295305115234
share|improve this answer
    
mmm isn't it 63? –  xem Jul 18 at 20:16
    
@xem: minor typographical error. Fixed. :D –  Kyle Kanos Jul 18 at 20:17
1  
Also works in GNU BC –  DigitalTrauma Jul 18 at 20:53
    
@DigitalTrauma: Probably works in several other languages too, I just stuck with Kona because I've answered in it before. –  Kyle Kanos Jul 18 at 20:54

Haskell, 5

Well, since nobody's posted a solution using actual maths, I decided I would, even though it's nowhere near as close as the other answers.

main=print$product[(1+1/r/(r+2))**2`logBase`r|r<-[1..99999999]]

This computes 2.6854453689859192, which is a whopping 5 characters of the constant. Wolfram was right when they said it is "difficult to calculate to high precision".

share|improve this answer
    
63 byte program - 1 byte to spare! Nice! –  DigitalTrauma Jul 18 at 21:04
    
The extra byte could be another 9, but my computer couldn't handle that and even if it could, I'm not sure whether it would result in another accurate digit. –  Zaq Jul 18 at 21:08

Mathematica, 6

(Times@@Rest@ContinuedFraction[Pi,977])^(1.`9/976)

gives

2.68545843

and uses only 50 bytes, so there is some room for finding something better than Pi and using a larger continued fraction, but I'm not sure it'll get a lot better with a runtime of an hour. (Especially since finding a better combination would probably take several days if I'm just using brute force.)

(Of course, you were clever enough to disallow Khinchin~N~2000, where 2000 could be replaced with any number that gives you a result within an hour ;).)

share|improve this answer
1  
+1 for using meaning of the constant, not just a formula. –  Vi. Jul 20 at 17:06

wxMaxima 3

An actually computed method!

bfloat(product((1+1/(n*(n+2)))^(log(n)/log(2)),n,1,10000));

After about 25 minutes, it returned

2.681499686663101b0

Now I understand why the Mathematica page stated that. I have 6 characters to play with, but I can't imagine adding 6 0's would (a) run in <60 min and (b) give me a more accurate solution.

share|improve this answer

GNU BC, 5 digits (54 byte program)

An attempt to actually calculate. GNU BC is horribly slow. This ran for 53 minutes on an Ubuntu 14.04 VM running on a mid-2012 MacBook Pro Retina. Strangely it runs faster in the VM than the OSX bare metal - presumably the GNU version is better optimised for this task than the BSD version.

for(k=r=1;r++<10^7;)k*=e(l(1/(r*(r+2))+1)*l(r)/l(2))
k

Output:

2.68544536902156538295

Note:

bc -l needs to be used for e() and l() functions (and setting scale = 20).

share|improve this answer

CJam floating point calculation - 6

1e8{I{1.II2+*/)I2mL#*}1.?}fI

It fits in the original 32 bytes :)

Running with the java interpreter using java 8, it outputs this after about a minute on my laptop:

2.6854513126595827

The online interpreter would probably take too long.

share|improve this answer

Python, 64 66

print"2.%i"%int('anljsgqif7gwwwsrntcz7zv2obv6gv5us7fzfwjcaj',36)

Outputs:

2.68545200106530644530971483548179569382038229399446295305115234555
share|improve this answer
    
You can cut the space after the print to squeeze in another character. –  xnor Jul 18 at 23:43
    
Nice catch, thanks. –  Dan Getz Jul 18 at 23:45

Ruby - 73

Unfortunately, you can only convert up to base 36 using to_i in Ruby:

"2.#{"hmegxpkvliy1vaw4lb054ep8wsqwkz2yx9cm9jvc9yfd48j".to_i 36}"

which returns

"2.6854520010653064453097148354817956938203822939944629530511523455572188595"
share|improve this answer

RPL/2, 7 calculated digits, 61 bytes

'LN(FLOOR(1/X))/(X+1)/LN(2)' { 'X' 1e-9 1 } 1e-7 INT DROP EXP

returns 2.68545210493822 in one minute on my old (intel Core2) laptop.

No Zeta function in RPL/2 as far as I know, this is why I have used the integration (formula 15 from the Mathworld page). In principle the accuracy could be improved by replacing 1e-9 and 1e-7 by smaller number, but I was apparently lacking memory for that.

Of course resorting to the infinite product solve this point, it looks like

1 1 1e9 FOR I 1 1 I dup 2 + * / + I LN 2 LN / ^ * NEXT

and shall work as is on an HP RPL calc, but it turns out to be two order of magnitude slower (on the laptop, didn't tried on my HP !), and gives only 6 digits.

So the integration algorithm in RPL/2 does quite a good job actually.

share|improve this answer

Many repl languages, 61

sorry, didn't find a better solution.

"2.685452001065306445309714835481795693820382293994462953051152"

The rules don't say that the correct number sequence can't be preceded by quotes, so I'm using this. By executing that in a JS console for example, you'll get the same string, including the quotes.

share|improve this answer
1  
Yes, this valid even with a quote in front. It only matters that the 2.685... is uninterrupted. –  Calvin's Hobbies Jul 18 at 20:39

Python (5)

x=3**.1
p=1
for _ in[1]*10**6:p*=(x//1)**1e-6;x=1/(x%1)
print(p)

Output: 2.6854396408091694

(Output takes ~2 seconds.)

In solidarity with the other math solutions, I'll give an even worse-converging one that computes the geometric mean of the first million continued fraction coefficients of a single arbitrary-ish irrational number that's not of a type known to not work. Actually, I rigged that number by trying a few until I got one that coincided on an extra digit.

Funny thing: I froze my computer and had to do a hard shutdown after trying to shorten this code with the Python golf trick of replacing for _ in[1]*10**6:code with exec("code"*10**6).

share|improve this answer

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.