Basado en esta pregunta de Math.SE ; número copiado de esta respuesta . Número originalmente de un video de Numberphile , por supuesto.
Su tarea es generar el siguiente número primo de 1350 dígitos:
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888111111111111111111111111888888111111111111111111111111888888111111811111111118111111888888111118811111111118811111888888111188811111111118881111888888111188811111111118881111888888111888811111111118888111888888111888881111111188888111888888111888888111111888888111888888111888888888888888888111888888111888888888888888888111888888111888888888888888888111888888811188888888888888881118888188811188888888888888881118881188881118888888888888811188881118888111888888888888111888811111888811118888888811118888111111188881111111111111188881111111118888111111111111888811111111111888811111111118888111111111111188881111111188881111111111111118888811118888811111111111111111888881188888111111111111111111118888888811111111111111111111111888888111111111111111111111111118811111111111111111111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Opcionalmente, puede incluir nuevas líneas en la salida.
Reglas
- Esto es complejidad kolmogorov , por lo que no hay entrada.
- Su programa debe finalizar dentro de una hora en una computadora estándar; si está cerca, usaré el mío para las pruebas. Si su programa se ejecuta por más de un minuto o no termina en TIO, incluya el tiempo en su computadora.
- Este es el código de golf , por lo que el código más corto, en bytes, gana.
code-golf
kolmogorov-complexity
primes
Stephen
fuente
fuente
Respuestas:
Gelatina ,
7471696866 bytesPruébalo en línea!
Cómo funciona
El literal
“©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’
reemplaza todos los caracteres con sus puntos de código en la página de códigos de Jelly e interpreta el resultado como un número (biyectivo) base-250, produciendo el siguiente entero.Luego,
ḃ19
convierte este número a la base biyectiva 19, produciendo la siguiente matriz de dígitos.Ahora,
ĖŒṙ
enumera los dígitos y realiza la decodificación de longitud de ejecución, produciendo la siguiente matriz.Luego,
ị⁾81
indexa en la cadena 81 , reemplazando números impares con el carácter 8 , número par con el carácter 1 . Posteriormente,s30
divide el resultado en fragmentos de longitud 30. Al mostrar un fragmento por línea, el resultado se ve de la siguiente manera.Ahora,
m0
concatena el conjunto de fragmentos con una copia invertida de sí mismo. Luego,Z
comprime el resultado, transponiendo filas y columnas.0
es un nilad no analizable, por lo que el resultado anterior se imprime (sin saltos de línea) y el valor de retorno se establece en 0 .62
es otro nilad no analizable, por lo que se imprime el resultado anterior ( 0 ) y el valor de retorno se establece en 62 .ȷ446
es otra nilad indescifrable. 62 se imprime y el valor de retorno se establece en 10 446 .Finalmente,
‘
incrementa el resultado. El resultado final ( 10 446 + 1 ) se imprime cuando finaliza el programa.fuente
[8, 1]
... Oh, eso es inteligente! Estoy robando este truco, espero que no te importe :))) y luego, sí, agrega todas esas cosas extrañas 06210..01. nice :)SOGL V0.12 ,
81787573 bytesPruébalo aquí!
Explicación:
fuente
Jalea , 136 bytes
Pruébalo en línea!
Explicación (números acortados)
-121 bytes gracias a Dennis usando
“...’
literales en lugar de números normalesfuente
“...’
Los literales guardan un montón de bytes. tio.run/…0;6;2;1;
Parece terriblemente prolijo.Gelatina ,
133 8473 bytesPruébalo en línea! (el pie de página formatea el número decimal con las dimensiones que dan el escudo de armas).
¿Cómo?
Una forma codificada de longitud de ejecución de un formato binario del lado izquierdo del escudo de armas
8
y1
hasta la fila antes de que la que comienza se0621
refleje con el0621
agregado y luego se multiplique por 10 446 y se incremente.fuente
De carbón ,
10710498968779 bytesPruébalo en línea! Enlace al código detallado para explicación
fuente
Protón , 368 bytes
Pruébalo en línea!
fuente
Rubí , 180 bytes.
Pruébalo en línea!
178 bytes + 2 bytes para
-Kn
(fuerza la codificación ASCII).43 caracteres en su mayoría no imprimibles entre las primeras comillas. Hexdump:
¿Cómo?
Todos los demás estaban haciendo codificación de longitud de ejecución, por lo que quería probar algo diferente.
La versión con formato de "imagen" de la prima se puede separar en dos partes: una cuadrícula de 30x30 de 8 y 1, y una segunda sección de ceros en su mayoría que se pueden codificar. Centrándonos en la primera parte, observamos que es simétrica en el centro, por lo que si podemos producir la mitad izquierda, podemos imprimir la mitad de cada línea con su reverso.
La mitad de una línea tiene 15 caracteres. Si reemplazamos los 8 con ceros, cada línea puede interpretarse como un número binario de 15 bits. Convenientemente, en su mayor parte, la distancia de edición entre cada línea consecutiva es pequeña, por lo que decidí implementar mi solución almacenando la primera línea
s
(888888888888888
que se convierte en 0) y aplicando una serie de operaciones de cambio de bitss
, imprimiendo el resultado cada vez .Como cada línea tiene 15 bits de longitud, codifiqué estas operaciones como dígitos hexadecimales; por ejemplo, si la operación es
b
(u 11), volteamos el bit 11. Algunas líneas difieren en más de un bit, por lo que requieren una cadena de hexadecimal dígitos Nos queda un bit (f
) para que podamos usarlo como un delimitador entre estas cadenas y también como un valor de "no hacer nada". Ejemplo a continuación (puede ver estas líneas en la publicación a la que se hace referencia en la pregunta):Para poner todo eso juntos, codificaríamos
0123456789ab
, luego nos separaríamosf
, no haríamos nadaf
, entonces5
. Esto funciona porque haremos.split(?f)
más adelante para obtener cada conjunto de operaciones por línea, lo que dará como resultado["0123456789ab", "", "5"]
, y""
será un no-op.La diferencia entre las líneas 3 y 4 anteriores es, con mucho, el conjunto más largo de ediciones, y la distancia de edición entre dos líneas consecutivas suele ser 0-2, por lo que diría que esta codificación es razonablemente económica, aunque estoy seguro de que puede Ser mejorado.
Toda la cadena codificada termina siendo
fff0123456789abff5f6f7ff8f4f3f012fff8bfef7af69df458cf01237bf6af59f48f237f16f045f3f12f0
(86 bytes), que obtendrá la cuadrícula completa de 30x30. Pero aún no hemos terminado ...Los dígitos hexadecimales se pueden representar con 4 bits (
b
->1100
, etc.) Eso significa que si estamos dispuestos a codificar nuestra cadena de 4 bits a la vez en lugar de usar bytes, podemos reducir la longitud de la cadena a la mitad. Entonces eso es lo que hice: el hexdump muestra la cadena representada en 43 bytes. Después de eso, es sólo una cuestión de usar ingeniosa de Ruby Cadena # deshacer las maletas conH*
(interpretar como cadena hexadecimal, nibble alto primero) para expandir la cadena de 43 bytes en la versión de 86 bytes que conocemos y amamos, y recorrer distintos conjunto de operaciones voltear bits: para nuestra cadena almacenadas
y una operaciónc
que hacemoss ^ 2**c.to_i(16)
para voltear el bit correspondiente.Después de completar cada conjunto de ediciones, rellenamos el binario resultante a 15 bits, cambiamos todos los 0 a 8 e imprimimos el resultado y su reverso. Como se señaló anteriormente, la parte del número después de la cuadrícula de 30x30 se puede codificar, por lo que hacemos eso como
puts'0621'+?0*445+?1
.La cadena codificada final no tiene posibilidad de trabajar en TIO, por lo que la versión TIO usa escapes, que aún funcionan pero son más largos.
fuente
Python 2 ,
760523329205196 bytes-237 bytes gracias a Stephen. -124 bytes gracias a Jonathan Frech.
Pruébalo en línea!
fuente
8
y1
y combinando621
621
. ¡Gracias!CJam,
532412340231210209 bytesPruébalo en línea
La codificación de longitud de ejecución se expandió desde la base 92 (la Base 250 condujo a caracteres multibyte, por lo que tuvo que ajustarse). Además,
4341089843357287864910309744850519376
se expande desde la base 92 y se convierte en binario. Un 1 significa que la longitud de ejecución es de dos dígitos, 0 significa que es un dígito. Por ejemplo, los primeros 4 dígitos de la representación binaria son 1101 porque las primeras cuatro ejecuciones son[93,8],[24,1],[6,8],[24,1]
(93 8, 24 1, etc.)fuente
JavaScript,
454450332207204 bytes-4 bytes gracias a Stephen. -125 bytes gracias a Shaggy y Dom Hastings.
Hay una gran cantidad de no imprimibles en esta respuesta, así que aquí hay un hexdump:
fuente
+'1'
ya que es unString
y+'0621'
puede ser+0+621
![...`]
meJavaScript (ES6),
206205204203198197194 bytesSe me ocurrió esto mientras trabajaba en la solución de i cri everytim , pensé que era lo suficientemente diferente como para justificar la publicación por sí mismo.
Esto incluye una carga de elementos no imprimibles entre
]
y,
luego siga el enlace TIO a continuación para verlo con escapes Unicode (cada secuencia\u
seguida de 4 dígitos cuenta como 1 byte).Pruébalo en línea
fuente
MATLAB / Octave ,
319318 bytesEste es mi primer intento en este desafío. Todavía es un poco grande y probablemente haya formas más eficientes de hacerlo, pero pensé en publicarlo de todos modos ya que el método era más interesante que simplemente comprimirlo.
Pruébalo en línea!
El método utilizado aquí es hacer uso de un esquema de codificación Run-Length-Encoding.
Comenzamos con el número original y contamos el número de dígitos consecutivos. Estos se escriben en el resultado a continuación como el recuento seguido directamente por el dígito (espacio separado para mayor claridad).
Si alguno de los valores es mayor que 95, lo dividimos en varios fragmentos de 95 o menos; esto solo sucede para los 445 0 que, en cambio, se convierten en cuatro conjuntos de 95 0 y un conjunto de 65 0. También rellenamos cualquier recuento que sea inferior a 10 con un 0 para que todos los elementos tengan tres caracteres de longitud. Esto cede con los espacios eliminados:
En retrospectiva en este punto, podría haber hecho este paso antes de fusionarlo todo, pero creo que vives y aprendes. Hacemos algo inteligente que consiste en tomar el recuento de cada grupo (2 dígitos) y sumamos 31. Debido a que todos ellos son <96, el número resultante es el valor ASCII para un carácter imprimible (32 a 126). Dándonos cuentas de:
Después de un poco de remodelación en MATLAB para hacerlo más favorable para la decodificación, y luego también escapar de los
'
caracteres con''
(de lo contrario, MATLAB divide los literales de cadena allí), nos queda la cadena inteligente:Esa es la raíz del código. En el código, todo lo que hago es reformar la matriz en una cadena 2D con 128 pares de caracteres. Para cada par, el primer personaje tiene 31 restados, y luego el segundo personaje se muestra tantas veces.
El resultado es el primo original:
Ediciones:
fuente
05AB1E , 76 bytes
Pruébalo en línea!
Esto le robó a Dennis:
Noté que siempre alterna entre 8 y 1, así que conté las longitudes de cada carrera (Base 20):
Lo uní todo y lo convirtió en un entero de base 10:
Comprimido más en base-255:
Luego, después de crear el bit comprimido ... Solo tenemos que manipularlo de nuevo al original ...
Salida final:
fuente
C (gcc) , 277 bytes
Tengo la sensación de que la cuerda podría acortarse de alguna manera.
Pruébalo en línea!
fuente
Perl 5 , 307 bytes
Pruébalo en línea!
fuente
Chicle , 88 bytes
Pruébalo en línea!
fuente
Ruby , 194 bytes
La parte superior está codificada en RLE, el resto simplemente está codificado.
Pruébalo en línea!
fuente
Kotlin , 339 bytes
Pruébalo en línea!
fuente
CJam (
10881 bytes)Demostración en línea
En caso de que la codificación de caracteres borre lo anterior, aquí está codificado xxd:
La ejecución inicial de 8s y 1s se divide solo en la mitad izquierda y la longitud de ejecución se codifica solo como la duración de las ejecuciones alternas. Las series de más de 24 se dividen en series de como máximo 24, separadas por series de 0, de modo que las longitudes pueden codificarse en base 25 y luego codificarse en base 256 para empacarlas.
fuente
JavaScript (ES2017), 287 bytes
Utiliza un enfoque ligeramente diferente a la respuesta de @icrieverytim . -10 bytes gracias a la sugerencia de @Shaggy de usar en
replace
lugar dematch
!fuente
/// , 260 bytes
Pruébalo en línea!
Nada terriblemente interesante, solo algo de compresión.
fuente
Mathematica, 192 bytes
Ver: http://reference.wolfram.com/language/ref/Compress.html
fuente
Python 2 ,
191190188 bytesPruébalo en línea!
El mismo director que mi respuesta aquí
fuente