Stała Khinchina do jak największej liczby miejsc po przecinku w 64 bajtach lub mniej

22

Stała Khinchina jest ciekawą stałą matematyczną, która według Wolframa MathWolda jest niezwykle trudna do obliczenia z dużą precyzją” .

Tutaj jest do 100 cyfr:

2.685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697 ...

Napisz program o długości 64 bajtów lub mniejszej, który wyświetla stałą Khinchina do maksymalnej liczby poprawnych miejsc po przecinku.

  • Nie możesz używać żadnych wbudowanych stałych bibliotecznych ani funkcji bezpośrednio związanych ze stałą Khinchina. (np. Math.Khinchin (precyzja) zdecydowanie nie jest dozwolona.)
  • Państwo może korzystać z bibliotek matematycznych do logarytmów obliczeniowych, podsumowań itp
  • Państwo może zakodować całości lub części odpowiedź.
  • Twój program musi generować skończone dane wyjściowe i działać w niecałą godzinę na rozsądnie nowoczesnym komputerze (takim jak wymienione tutaj ).
  • Musisz wyprowadzać na standardowe wyjście. Brak danych wejściowych.
  • Możesz użyć dowolnych znaków, o ile http://mothereff.in/byte-counter rejestruje 64 bajty lub mniej.

Punktacja

Twój wynik to liczba kolejnych cyfr w stałej Khinchina, którą program poprawnie wypisuje, zaczynając od 2,68 ... Możesz wypisać niepoprawne cyfry, ale tylko ostatnia poprawna cyfra jest liczona do wyniku.

Na przykład wyjście

2,68545200 2 06530644530971483548179569382038229399446295305115234555721

zdobyłby 9 punktów. Jedna dla każdej cyfry, 2 6 8 5 4 5 2 0 0ale nic po 2 nie powinno być 1.

Hobby Calvina
źródło
2
Dlaczego zezwalasz na kodowanie całej odpowiedzi?
William Barbosa
5
@WilliamBarbosa dlaczego nie? idealnie byłoby rozwiązanie, które uzyska wynik lepszy niż 31. jeśli nie, to niefortunne.
Martin Ender
1
Czy dozwolony jest Unicode? Jak to policzyć?
aditsu
3
Powinieneś zezwolić na 64b zamiast 32 i liczyć wszystkie znaki jako bajty UTF-8 ( mothereff.in/byte-counter ) (= 1 do 4 bajtów na znak w zależności od płaszczyzny Unicode). Ponadto istniejące rozwiązania można łatwo dostosować do wersji 64b
xem
3
@PeterTaylor Kodowałem rozwiązanie zmiennoprzecinkowe CJam i powiem ci, że ograniczona precyzja nie jest głównym problemem: p
aditsu

Odpowiedzi:

11

Klon, 200+

Następujące polecenie Maple oblicza stałą Khinchina z żądaną precyzją (tutaj 200 cyfr):

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

Ten kod powinien działać, jeśli skopiujesz go i wkleisz do interfejsu graficznego Maple. ζMa dwa bajty w UTF-8, i trzy, w sumie 62 bajtów.

Napisanie wersji tych symboli ASCII, nawet przy użyciu sztuczki polegającej na użyciu min()zamiast infinity, niestety, zwiększa liczbę bajtów do 66:

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

Liczbę obliczonych cyfr można łatwo dostosować, zmieniając liczbę w nawiasach kwadratowych po evalf. Na moim raczej starym komputerze 200 cyfr kończy się za około pół godziny; twój może być w stanie więcej. Zauważ, że Maple zaokrągla wynik do żądanej precyzji zamiast go obcinać, więc faktyczna liczba pasujących cyfr może być nieco mniejsza.

Ta metoda obliczania stałej oparta jest na wzorze (9) ze strony MathWorld , cytowanej tam w Gosper (1996, pers. Comm.):

            Equation

To była najbardziej wydajna metoda, którą udało mi się (ledwo) wycisnąć do 64 bajtów lub mniej.

Ilmari Karonen
źródło
Całkiem schludnie. Gdybym tylko miał Maple: /
Hobby Calvina
12

CJam - 118

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

Wypróbuj na http://cjam.aditsu.net/

Ponieważ stackexchange niszczy niektóre znaki, oto program, który generuje program powyżej; uruchom go najpierw, a następnie uruchom dane wyjściowe:

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

Wyjaśnienie:

2pcha 2
'.pcha kropka
"…"to ciąg zawierający resztę cyfr w postaci zakodowanej
128bkonwertuje ciąg na liczbę, traktując znaki jak cyfry w bazie 128 (poprzez ich kod ASCII)

aditsu
źródło
2
Bardzo dobrze. Czy możesz to trochę wyjaśnić?
Kyle Kanos
@KyleKanos dodał wyjaśnienie
aditsu
To cudownie. Powinienem nauczyć się CJam pewnego dnia ... Poza tym nie mogę zmusić twojego internetowego tłumacza do pracy w przeglądarce Opera, chociaż działa na moim Firefoksie. Prawdopodobnie problem Opery, ale pomyślałem, że o tym wspomnę.
Kyle Kanos
1
@ Calvin'sHobbies W 1997 roku Xavier Gourdon obliczył pierwsze 110 000 cyfr w ciągu 22 godzin przy użyciu co najwyżej procesora 250 MHz. Być może będziesz w stanie obliczyć 1000 razy więcej cyfr niż to rozwiązanie w ciągu godziny. web.archive.org/web/20120218093629/http://pi.lacim.uqam.ca/…
Alex L
1
@ Hobby Calvina zobacz ten link, aby uzyskać pełny program, który podobno obliczył 2000 cyfr w 7 sekund.
aditsu
5

Kona 63

Prosta, zakodowana odpowiedź:

2.68545200106530644530971483548179569382038229399446295305115234
Kyle Kanos
źródło
mmm, czy to nie 63?
xem.
@xem: drobny błąd typograficzny. Naprawiony. : D
Kyle Kanos
1
Działa również w GNU BC
Digital Trauma
@DigitalTrauma: Prawdopodobnie działa również w kilku innych językach, po prostu utknąłem z Kona, ponieważ odpowiedziałem wcześniej.
Kyle Kanos
5

Haskell, 5

Cóż, ponieważ nikt nie opublikował rozwiązania z wykorzystaniem faktycznych obliczeń matematycznych, postanowiłem, że tak zrobię, nawet jeśli nie jest tak blisko, jak inne odpowiedzi.

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

To oblicza 2.6854453689859192, czyli aż 5 znaków stałej. Wolfram miał rację, gdy powiedzieli, że „trudno jest obliczyć z dużą precyzją”.

Zaq
źródło
Program 63-bajtowy - 1 bajt do stracenia! Miły!
Cyfrowa trauma
Dodatkowy bajt może być inny 9, ale mój komputer nie mógł sobie z tym poradzić, a nawet gdyby mógł, nie jestem pewien, czy spowodowałoby to kolejną dokładną cyfrę.
Zaq
Korzystając z Ruby, w zasadzie osiągnąłem maksimum, jakie można zrobić przy użyciu tej formuły, uruchamiając to w 60 sekund. Mam 2.685451312659854: tio.run
Po prostu piękna sztuka
3

Mathematica, 6

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

daje

2.68545843

i zużywa tylko 50 bajtów, więc jest miejsce na znalezienie czegoś lepszego niż Pii użycie większej ciągłej frakcji, ale nie jestem pewien, czy poprawi się znacznie z czasem działania. (Zwłaszcza, że znalezienie lepszej kombinacji prawdopodobnie potrwa kilka dni, jeśli użyję tylko brutalnej siły).

(Oczywiście, byłeś wystarczająco sprytny, aby to zabronić Khinchin~N~2000, gdzie 2000można zastąpić dowolną liczbą, która daje wynik w ciągu godziny;).)

Martin Ender
źródło
1
+1 za użycie znaczenia stałej, a nie tylko formuły.
Vi.
2

wxMaxima 3

Faktycznie obliczona metoda!

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

Po około 25 minutach wrócił

2.681499686663101b0

Teraz rozumiem, dlaczego strona Mathematica to powiedziała. Mam 6 znaków do zabawy, ale nie wyobrażam sobie, aby dodanie 6 0 (a) działało w <60 min i (b) dawało mi dokładniejsze rozwiązanie.

Kyle Kanos
źródło
Podejrzenie: Każde dodatkowe zero dodaje mniej niż jedną poprawną cyfrę: „(
Po prostu piękna sztuka
1

GNU BC , 5 cyfr (program 54-bajtowy)

Próba faktycznego obliczenia. GNU BC jest strasznie wolny. Trwało to 53 minuty na maszynie Wirtualnej Ubuntu 14.04 działającej na MacBooku Pro Retina z połowy 2012 roku. O dziwo działa szybciej na maszynie wirtualnej niż OSX bez metalu - przypuszczalnie wersja GNU jest lepiej zoptymalizowana do tego zadania niż wersja BSD.

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

Wydajność:

2.68544536902156538295

Uwaga:

bc -lmusi być użyty e()i l()funkcje (i ustawienie skali = 20).

Cyfrowa trauma
źródło
1

Obliczanie zmiennoprzecinkowe CJam - 6

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

Pasuje do oryginalnych 32 bajtów :)

Działa z interpreterem Java przy użyciu java 8, wyświetla to po około minucie na moim laptopie:

2.6854513126595827

Tłumacz online prawdopodobnie potrwa zbyt długo.

aditsu
źródło
1

Python, 64 66

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

Wyjścia:

2.68545200106530644530971483548179569382038229399446295305115234555
Dan Getz
źródło
Możesz wyciąć przestrzeń po, printaby ścisnąć inną postać.
xnor
1

Rubin - 73

Niestety, możesz przekonwertować do bazy 36 tylko to_iw Ruby:

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

który zwraca

"2.6854520010653064453097148354817956938203822939944629530511523455572188595"
OI
źródło
1

RPL / 2, 7 cyfr obliczeniowych, 61 bajtów

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

zwraca 2.68545210493822 w ciągu jednej minuty na moim starym laptopie (Intel Core2).

O ile mi wiadomo, nie ma funkcji Zeta w RPL / 2, dlatego użyłem integracji (wzór 15 ze strony Mathworld). Zasadniczo dokładność można poprawić, zastępując 1e-9 i 1e-7 mniejszą liczbą, ale najwyraźniej brakowało mi na to pamięci.

Oczywiście uciekanie się do nieskończonego produktu rozwiązuje ten problem, wygląda na to

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

i będzie działać tak, jak na HP RPL calc, ale okazuje się, że jest o dwa rzędy wielkości wolniejsze (na laptopie, nie próbowałem na moim HP!) i daje tylko 6 cyfr.

Tak więc algorytm integracji w RPL / 2 wykonuje całkiem niezłą robotę.

Masa perłowa
źródło
0

Wiele języków zastępczych, 61

przepraszam, nie znalazłem lepszego rozwiązania.

"2.685452001065306445309714835481795693820382293994462953051152"

Reguły nie mówią, że poprawnej sekwencji numerów nie można poprzedzać cudzysłowami, więc używam tego. Wykonując to na przykład w konsoli JS, otrzymasz ten sam ciąg znaków, łącznie z cudzysłowami.

Xem
źródło
1
Tak, to ważne nawet z cytatem z przodu. Ważne jest tylko to, że 2.685 ... jest nieprzerwany.
Calvin's Hobbies
0

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

(Wyjście zajmuje ~ 2 sekundy.)

W ramach solidarności z innymi rozwiązaniami matematycznymi dam jeszcze gorsze zbieżne rozwiązanie, które oblicza średnią geometryczną pierwszego miliona stałych współczynników ułamkowych pojedynczej dowolnej liczby niewymiernej, która nie jest typu, o którym wiadomo, że nie działa. Tak naprawdę, poprawiłem ten numer, próbując kilku, aż dostałem taki, który zbiegł się z dodatkową cyfrą.

Zabawne: zamroziłem komputer i musiałem mocno zamknąć komputer, próbując skrócić ten kod, stosując golfową sztuczkę Pythona polegającą na zastąpieniu for _ in[1]*10**6:codego exec("code"*10**6).

xnor
źródło
0

ES7, 56

alert`2.6854520010653064453097148354817956938203822939944629531`
elipszilon
źródło