Específicamente, el PRIMEGAME de Conway .
Este es un algoritmo ideado por John H. Conway para generar números primos usando una secuencia de 14 números racionales:
A B C D E F G H I J K L M N
17 78 19 23 29 77 95 77 1 11 13 15 15 55
-- -- -- -- -- -- -- -- -- -- -- -- -- --
91 85 51 38 33 29 23 19 17 13 11 14 2 1
Por ejemplo, F es la fracción 77/29
.
Así es como el algoritmo encuentra los números primos. Comenzando con el número 2
, encuentre la primera entrada en la secuencia que, cuando se multiplica, produce un número entero. Aquí es M
, 15/2
que produce 15
. Luego, para ese número entero 15
, encuentre la primera entrada en la secuencia que cuando se multiplica produce un número entero. Ese es el último N
, o 55/1
, que rinde 825
. Escribe la secuencia correspondiente. (El astuto entre ustedes puede reconocer esto como un programa FRACTRAN ).
Después de algunas iteraciones, obtendrá lo siguiente:
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4 ...
Tenga en cuenta que el último elemento de la lista es 4
, o 2^2
. ¡Mira nuestro primer número primo (el 2
exponente) generado con este algoritmo! Finalmente, la secuencia tendrá el siguiente aspecto:
2 ... 2^2 ... 2^3 ... 2^5 ... 2^7 ... etc.
Por lo tanto, arrojando los números primos. Este es OEIS A007542 .
El reto
Dado un número de entrada n
, ya sea cero o uno indexado (su elección), puede generar los primeros n
números de esta secuencia o generar el n
número th de esta secuencia.
Ejemplos
Los siguientes ejemplos muestran el n
término th de la secuencia indexada a cero.
n output
5 2275
19 4
40 408
Reglas
- Si corresponde, puede suponer que la entrada / salida se ajustará al tipo entero nativo de su idioma.
- La entrada y salida se pueden dar por cualquier método conveniente .
- Un programa completo o una función son aceptables. Si es una función, puede devolver el resultado en lugar de imprimirlo.
- Las lagunas estándar están prohibidas.
- Este es el código de golf, por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).
fuente
408.0
en lugar de408
por ejemplo.Respuestas:
Python 3 ,
173 165 153 145 144 136 135 127 126 125 108 107104 bytesPruébalo en línea!
2>>n*2
es2
paran==0
y de lo0
contrario.103 bytes si podemos devolver flotantes.
fuente
FRACTRAN , 99 bytes
Pruébalo en línea!
El programa toma
2*31^n
como entrada, que se utiliza como estado inicial.Todas las fracciones en el programa FRACTRAN original se han dividido entre 31 (el primer registro principal no utilizado), por lo que el programa se detiene en la enésima iteración.
fuente
Jalea ,
4943 bytesPruébalo en línea!
fuente
0ọ0¤
esinf
, de lo contrario podría haber reducido este a 42 bytes ...Python 3 , 107 bytes
Pruébalo en línea!
Codifica la lista de fracciones
zip
incorporando dos cadenas de bytes que contienen caracteres ASCII bajos no imprimibles.Si
n
es cero, devolvemos el argumentok
; de lo contrario, recurrimos con nuevos parámetros. Nuestro nuevok
es el primer valork*a//b
correspondiente a alguna fracción(a, b)
de la lista, de modo quek*a//b
sea un número entero, es decirk*a%b<1
.fuente
MATL , 50 bytes
Pruébalo en línea!
fuente
Hi:
... aww, "Hola" a ti también, código. :-)J ,
116110 bytesPruébalo en línea!
0 indexado; devuelve el enésimo número
Algunos bytes se pueden guardar haciendo que el verbo sea tácito, pero tengo problemas para que
^:
funcione.Explicación:
J describe los números racionales en la forma NrD, donde N es el numerador y D es el denominador, por ejemplo
17r91 78r85 19r51 23r38...
, creé 2 listas separadas para los numeradores y denominadores e hice 2 números base-96 a partir de ellos.1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x
convierte los números de base 96 en listas y construye una lista de fracciones dividiendo las dos listas.2
comenzar con 2^:y
repite el verbo a la izquierdan
(y es el argumento de la función)]
el argumento correcto (comienza en 2 y luego usa el resultado de cada iteración)*
multiplicar la lista de fracciones por el argumento correcto(=<.)
son los resultados enteros (compare cada número con su piso){.@I.@
encuentra el índiceI.
del primero{.
de los enteros{[
usa el índice para recuperar el númerofuente
('0m26<l~l *,..V'%&(31x-~3&u:)'ztRE@<620,*-! ')&(0{*#~0=1|*)2:
05AB1E ,
4443 bytes0 indexado
Pruébalo en línea!
Explicación
El gran número empujado es
17781923297795770111131515559185513833292319171311140201
fuente
Pari / GP , 121 bytes
Pruébalo en línea!
fuente
JavaScript (Node.js) ,
10695 bytesPruébalo en línea!
fuente
Buffer
. Además, creo que es seguro poner todos los datos en un solo búfer: 95 bytes .Retina , 213 bytes
Pruébalo en línea! Explicación:
Reemplace la entrada con una lista de todas las fracciones, más el entero inicial.
Convierte todo a unario.
Repita la sustitución la cantidad de veces dada por la entrada original.
Encuentre un denominador que divida uniformemente el número entero.
Reemplace el entero con el resultado de la división multiplicada por el numerador.
Convierta el entero a decimal y genere el resultado.
fuente
Adjunto , 81 bytes
Pruébalo en línea! Produce una fracción sobre 1. Por ejemplo, la entrada
5
devuelve2275/1
. Esto se puede solucionar con más 2 bytes al anteponerN@
al programa.Explicación
Esta es una función currificada, que curry
Nest
con dos argumentos predefinidos:y
2
. Este último argumento es simplemente la semilla inicial, y el argumento que se pasa a esta función es el número de iteraciones para anidar la función dada.Lo siguiente se usa para codificar PRIMEGAME:
Esto se evalúa como tal:
Reemplacemos esta expresión con
G
en la explicación. Nuestra primera función se convierte en:Esto realiza una única iteración del código FRACTRAN
_
, la entrada a la función. EsFind
unIntegral
miembro (uno que es un entero) de la matriz_*G
, que es la entrada_
multiplicada con cada miembro deG
.Nest
simplemente aplica esta transformación el número dado de veces.Adjunto, 42 bytes
Implementé partes de la
$langs
biblioteca, inspirándome en este desafío, así que marco esta sección como no competitiva.Esto simplemente consulta la lista de
FRACTRAN_EXAMPLES
que tengo. Cada ejemplo es unaFractranExample
instancia, que llama a laFRACTRAN
función incorporada . Elprime
ejemplo es el PRIMEGAME de Conway.fuente
F # (Mono) , 215 bytes
Pruébalo en línea!
fuente
PHP, 183 bytes (189 con etiqueta "php")
Golfizado:
Sin golf:
Pruébalo en línea!
fuente