22
\$\begingroup\$

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.

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Why are you allowing hardcoding the entire answer? \$\endgroup\$ – William Barbosa Jul 18 '14 at 18:07
  • 5
    \$\begingroup\$ @WilliamBarbosa why not? ideally there should be a solution that scores better than 31. if not, well that's unfortunate. \$\endgroup\$ – Martin Ender Jul 18 '14 at 18:11
  • 1
    \$\begingroup\$ Is unicode allowed? How to count it? \$\endgroup\$ – aditsu Jul 18 '14 at 18:42
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – xem Jul 18 '14 at 19:57
  • 3
    \$\begingroup\$ @PeterTaylor I coded a CJam floating-point solution, and let me tell you, limited precision is not the main problem :p \$\endgroup\$ – aditsu Jul 18 '14 at 20:06

14 Answers 14

11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Pretty neat. If only I had Maple :/ \$\endgroup\$ – Calvin's Hobbies Jul 20 '14 at 9:40
12
\$\begingroup\$

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)

\$\endgroup\$
  • 2
    \$\begingroup\$ Very nice. Can you explain it a bit? \$\endgroup\$ – Kyle Kanos Jul 18 '14 at 19:01
  • \$\begingroup\$ @KyleKanos added explanation \$\endgroup\$ – aditsu Jul 18 '14 at 19:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Kyle Kanos Jul 18 '14 at 19:12
  • 1
    \$\begingroup\$ @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/… \$\endgroup\$ – Alex L Jul 20 '14 at 10:54
  • 1
    \$\begingroup\$ @Calvin'sHobbies see this link for a complete program that reportedly calculated 2000 digits in 7 seconds. \$\endgroup\$ – aditsu Jul 20 '14 at 12:31
5
\$\begingroup\$

Kona 63

Simple hard-coded answer:

2.68545200106530644530971483548179569382038229399446295305115234
\$\endgroup\$
  • \$\begingroup\$ mmm isn't it 63? \$\endgroup\$ – xem Jul 18 '14 at 20:16
  • \$\begingroup\$ @xem: minor typographical error. Fixed. :D \$\endgroup\$ – Kyle Kanos Jul 18 '14 at 20:17
  • 1
    \$\begingroup\$ Also works in GNU BC \$\endgroup\$ – Digital Trauma Jul 18 '14 at 20:53
  • \$\begingroup\$ @DigitalTrauma: Probably works in several other languages too, I just stuck with Kona because I've answered in it before. \$\endgroup\$ – Kyle Kanos Jul 18 '14 at 20:54
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 63 byte program - 1 byte to spare! Nice! \$\endgroup\$ – Digital Trauma Jul 18 '14 at 21:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Zaq Jul 18 '14 at 21:08
  • \$\begingroup\$ Using Ruby, I basically hit the maximum one could do using this formula, running this in 60 seconds. I got 2.685451312659854: tio.run/##KypNqvz/P9vWkEvDUE/… \$\endgroup\$ – Simply Beautiful Art Nov 28 '17 at 1:04
3
\$\begingroup\$

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 ;).)

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for using meaning of the constant, not just a formula. \$\endgroup\$ – Vi. Jul 20 '14 at 17:06
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Suspicion: Each additional zero adds less than one more correct digit :'( \$\endgroup\$ – Simply Beautiful Art Nov 28 '17 at 0:56
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Python, 64 66

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

Outputs:

2.68545200106530644530971483548179569382038229399446295305115234555
\$\endgroup\$
  • \$\begingroup\$ You can cut the space after the print to squeeze in another character. \$\endgroup\$ – xnor Jul 18 '14 at 23:43
1
\$\begingroup\$

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"
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yes, this valid even with a quote in front. It only matters that the 2.685... is uninterrupted. \$\endgroup\$ – Calvin's Hobbies Jul 18 '14 at 20:39
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

ES7, 56

alert`2.6854520010653064453097148354817956938203822939944629531`
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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