La constante de Khinchin a tantos decimales como sea posible en 64 bytes o menos

22

La constante de Khinchin es una constante matemática curiosa que, según Wolfram MathWold , es "notablemente difícil de calcular con alta precisión" .

Aquí está a 100 dígitos:

2.685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697 ...

Escriba un programa en 64 bytes o menos que envíe la constante de Khinchin al número máximo de decimales correctos.

  • No puede usar ninguna función o constante de biblioteca integrada directamente relacionada con la constante de Khinchin. (por ejemplo, Math.Khinchin (precisión) definitivamente no está permitido).
  • Usted puede utilizar las bibliotecas de matemáticas para los logaritmos de cómputo, sumatorias, etc.
  • Usted puede codificar toda o parte de su respuesta.
  • Su programa debe producir resultados finitos y ejecutarse en menos de una hora en una computadora razonablemente moderna (como las que se enumeran aquí ).
  • Debe enviar a stdout. No hay entrada
  • Puede usar los caracteres que desee siempre que http://mothereff.in/byte-counter registre 64 bytes o menos.

Tanteo

Su puntaje es el número de dígitos sucesivos en la constante de Khinchin que su programa genera correctamente, comenzando con 2.68 ... Puede generar dígitos incorrectos pero solo se cuenta el último dígito correcto para su puntaje.

Por ejemplo, una salida de

2.68545200 2 06530644530971483548179569382038229399446295305115234555721

anotaría 9 puntos. Uno para cada uno de los dígitos 2 6 8 5 4 5 2 0 0pero nada después del 2 que debería ser un 1.

Pasatiempos de Calvin
fuente
2
¿Por qué estás permitiendo codificar la respuesta completa?
William Barbosa
55
@WilliamBarbosa ¿por qué no? idealmente debería haber una solución que tenga un puntaje mejor que 31. si no, bueno, eso es lamentable.
Martin Ender
1
¿Está permitido unicode? ¿Cómo contarlo?
aditsu
3
Debería permitir 64b en lugar de 32, y contar todos los caracteres como bytes UTF-8 ( mothereff.in/byte-counter ) (= 1 a 4 bytes por char dependiendo del plano Unicode). Además, las soluciones existentes podrían adaptarse fácilmente a 64b
xem
3
@PeterTaylor Codifiqué una solución de punto flotante CJam, y déjame decirte que la precisión limitada no es el problema principal: p
aditsu

Respuestas:

11

Arce, más de 200

El siguiente comando Maple calcula la constante de Khinchin con la precisión solicitada (aquí, 200 dígitos):

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

Este código debería funcionar si lo copia y pega en la interfaz gráfica de Maple. El ζtoma dos bytes en UTF-8, y los tres, para un total de 62 bytes.

Escribir las versiones ASCII de esos símbolos, incluso con el truco de usar en min()lugar de infinity, por desgracia, lleva el recuento de bytes hasta 66:

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

El número de dígitos calculados se puede ajustar fácilmente cambiando el número entre corchetes después evalf. En mi computadora bastante vieja, 200 dígitos parecen terminar en aproximadamente media hora; el tuyo podría ser capaz de más. Tenga en cuenta que Maple redondea el resultado a la precisión solicitada en lugar de truncarlo, por lo que el número real de dígitos coincidentes podría ser algo menor.

Este método de cálculo de la constante se basa en la fórmula (9) de la página MathWorld , citada allí a Gosper (1996, comunicación personal):

            Ecuación

Este fue el método más eficiente que logré (apenas) exprimir en 64 bytes o menos.

Ilmari Karonen
fuente
Con buena pinta. Si solo tuviera Arce: /
Calvin's Hobbies
12

CJam - 118

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

Pruébalo en http://cjam.aditsu.net/

Como stackexchange destruye algunos de los caracteres, aquí hay un programa que genera el programa anterior; ejecutarlo primero, luego ejecutar su salida:

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

Explicación:

2empuja 2
'.empuja el punto
"…"es una cadena que contiene el resto de los dígitos en forma codificada
128bconvierte la cadena en un número, tratando los caracteres como dígitos en la base 128 (a través de su código ASCII)

aditsu
fuente
2
Muy agradable. ¿Puedes explicarlo un poco?
Kyle Kanos
@KyleKanos agregó explicación
aditsu
Eso es genial. Debería aprender CJam algún día ... Además, no puedo hacer que tu intérprete en línea funcione en el navegador web Opera, aunque funciona en mi Firefox. Probablemente un problema de Opera, pero pensé en mencionarlo.
Kyle Kanos
1
@ Calvin'sHobbies En 1997, Xavier Gourdon calculó los primeros 110,000 dígitos en 22 horas utilizando como máximo un procesador de 250MHz. Por lo tanto, es posible que pueda calcular 1000 veces más dígitos que esta solución en una hora. web.archive.org/web/20120218093629/http://pi.lacim.uqam.ca/…
Alex L
1
@ Calvin'sHobbies ve este enlace para un programa completo que supuestamente calculó 2000 dígitos en 7 segundos.
aditsu
5

Kona 63

Respuesta simple codificada:

2.68545200106530644530971483548179569382038229399446295305115234
Kyle Kanos
fuente
mmm no es 63?
xem
@xem: error tipográfico menor. Fijo. : D
Kyle Kanos
1
También trabaja en GNU BC
Digital Trauma
@DigitalTrauma: Probablemente también funcione en varios otros idiomas, simplemente me quedé con Kona porque ya he respondido antes.
Kyle Kanos
5

Haskell, 5

Bueno, dado que nadie ha publicado una solución usando matemáticas reales, decidí que lo haría, a pesar de que no está tan cerca como las otras respuestas.

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

Esto calcula 2.6854453689859192, que son la friolera de 5 caracteres de la constante. Wolfram tenía razón cuando dijeron que es "difícil de calcular con alta precisión".

Zaq
fuente
Programa de 63 bytes - ¡1 byte de sobra! ¡Agradable!
Digital Trauma
El byte adicional podría ser otro 9, pero mi computadora no podría manejar eso e incluso si pudiera, no estoy seguro de si daría como resultado otro dígito preciso.
Zaq
Usando Ruby, básicamente alcancé el máximo que podría hacer con esta fórmula, ejecutándola en 60 segundos. Tengo 2.685451312659854: tio.run/##KypNqvz/P9vWkEvDUE/...
Simply Beautiful Art
3

Mathematica, 6

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

da

2.68545843

y usa solo 50 bytes, por lo que hay espacio para encontrar algo mejor Piy usar una fracción continua más grande, pero no estoy seguro de que mejore mucho con un tiempo de ejecución de una hora. (Especialmente porque encontrar una mejor combinación probablemente tomaría varios días si solo uso la fuerza bruta).

(Por supuesto, fuiste lo suficientemente inteligente como para no permitir Khinchin~N~2000, donde 2000podría ser reemplazado por cualquier número que te dé un resultado en una hora;).)

Martin Ender
fuente
1
+1 por usar el significado de la constante, no solo una fórmula.
Vi.
2

wxMaxima 3

¡Un método realmente calculado!

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

Después de unos 25 minutos, regresó

2.681499686663101b0

Ahora entiendo por qué la página de Mathematica dice eso. Tengo 6 personajes para jugar, pero no puedo imaginar que agregar 6 0 (a) se ejecute en <60 min y (b) me dé una solución más precisa.

Kyle Kanos
fuente
Sospecha: Cada cero adicional agrega menos de un dígito correcto más: '(
Simply Beautiful Art,
1

GNU BC , 5 dígitos (programa de 54 bytes)

Un intento de calcular realmente. GNU BC es horriblemente lento. Esto funcionó durante 53 minutos en una máquina virtual Ubuntu 14.04 que se ejecuta en una MacBook Pro Retina de mediados de 2012. Curiosamente, se ejecuta más rápido en la VM que en el OSX bare metal: presumiblemente, la versión GNU está mejor optimizada para esta tarea que la versión BSD.

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

Salida:

2.68544536902156538295

Nota:

bc -lnecesita ser utilizado para e()y l()funciones (y ajuste scale = 20).

Trauma digital
fuente
1

CJam cálculo de coma flotante - 6

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

Encaja en los 32 bytes originales :)

Ejecutando con el intérprete de java usando java 8, genera esto después de aproximadamente un minuto en mi computadora portátil:

2.6854513126595827

El intérprete en línea probablemente tomaría demasiado tiempo.

aditsu
fuente
1

Python, 64 66

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

Salidas:

2.68545200106530644530971483548179569382038229399446295305115234555
Dan Getz
fuente
Puede cortar el espacio después printde exprimir a otro personaje.
xnor
1

Rubí - 73

Desafortunadamente, solo puedes convertir hasta la base 36 usando to_ien Ruby:

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

que vuelve

"2.6854520010653064453097148354817956938203822939944629530511523455572188595"
OI
fuente
1

RPL / 2, 7 dígitos calculados, 61 bytes

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

devuelve 2.68545210493822 en un minuto en mi vieja computadora portátil (Intel Core2).

Hasta donde yo sé, no hay ninguna función Zeta en RPL / 2, es por eso que he usado la integración (fórmula 15 de la página de Mathworld). En principio, la precisión podría mejorarse reemplazando 1e-9 y 1e-7 por un número más pequeño, pero aparentemente me faltaba memoria para eso.

Por supuesto, recurrir al producto infinito para resolver este punto, parece que

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

y funcionará como está en una calculadora HP RPL, pero resulta ser dos orden de magnitud más lenta (en la computadora portátil, ¡no lo probé en mi HP!), y solo da 6 dígitos.

Por lo tanto, el algoritmo de integración en RPL / 2 hace un buen trabajo en realidad.

Nácar
fuente
0

Muchos idiomas de respuesta, 61

lo siento, no encontré una solución mejor.

"2.685452001065306445309714835481795693820382293994462953051152"

Las reglas no dicen que la secuencia numérica correcta no puede ser precedida por comillas, así que estoy usando esto. Al ejecutar eso en una consola JS, por ejemplo, obtendrá la misma cadena, incluidas las comillas.

xem
fuente
1
Sí, esto es válido incluso con una cita por adelantado. Solo importa que el 2.685 ... sea ininterrumpido.
Hobbies de Calvin
0

Pitón (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

(La salida tarda ~ 2 segundos).

En solidaridad con las otras soluciones matemáticas, daré una convergencia aún peor que calcula la media geométrica del primer millón de coeficientes de fracción continua de un solo número irracional arbitrario que no es de un tipo que se sabe que no funciona. En realidad, manipulé ese número probando algunos hasta que obtuve uno que coincidió con un dígito adicional.

Lo curioso: me congeló mi equipo y tuvo que hacer una parada dura después de tratar de acortar este código con el truco de golf del pitón de reemplazar for _ in[1]*10**6:codecon exec("code"*10**6).

xnor
fuente
0

ES7, 56

alert`2.6854520010653064453097148354817956938203822939944629531`
elipszilon
fuente