Definición
Llamemos universal a una secuencia entera (infinita) si contiene cada secuencia entera finita como una subsecuencia contigua.
En otras palabras, la secuencia entera (a 1 , a 2 , ...) es universal si y solo si, para cada secuencia entera finita (b 1 , ..., b n ) , hay un desplazamiento k tal que (a k + 1 , ..., a k + n ) = (b 1 , ..., b n ) .
La secuencia de números primos positivos, por ejemplo, no es universal, entre otras, por las siguientes razones.
No contiene enteros negativos, 1 o números compuestos.
Aunque contiene 3 , no contiene la subsecuencia contigua (3, 3, 3) .
Aunque contiene 2 y 5 , no contiene la subsecuencia contigua (2, 5) .
Aunque contiene la subsecuencia contigua (7, 11, 13) , no contiene la subsecuencia contigua (13, 11, 7) .
Tarea
Elija cualquier secuencia entera universal (un 1 , un 2 , ...) e impleméntela en el lenguaje de programación que elija, respetando las siguientes reglas.
Puede enviar un programa completo o una función.
Tiene tres opciones para E / S:
No ingrese datos e imprima o devuelva la secuencia completa.
Tome un índice n como entrada e imprima o devuelva un n .
Tome un índice n como entrada e imprima o devuelva (un 1 , ..., un n ) .
Para las opciones de E / S 2 y 3 , puede usar la indexación basada en 0 si lo prefiere.
Su envío debe ser determinista: si se ejecuta varias veces con la misma entrada, debe producir la misma salida.
Además, a menos que sea inmediatamente obvio, pruebe que la secuencia que eligió es universal. Su prueba puede no depender de conjeturas no comprobadas.
Aplican reglas estándar de código de golf . ¡Que gane el código más corto en bytes!
Respuestas:
Casco , 5 bytes
Esto imprime una lista infinita
Pruébalo en línea! o encuentre el primer índice de su secuencia . (Toma mucha memoria para la mayoría de las secuencias)
Explicación:
En Husk se
Ṗ
comporta muy bien para listas infinitas. Puedes ver su comportamiento aquífuente
Q
funciona. (Creo que lo tengo, pero no estoy seguro.)Ṗ
, noQ
Python 2 ,
494643 bytesf(n)
devuelve una n solamente. Utiliza el dígito más pequeño den
in based
para extraer uno de los dígitos más altos.Pruébalo en línea! Este guión (cortesía de Dennis) toma cualquier secuencia finita y le da un lugar
n
donde comienza esa secuencia.Explicación
Por ejemplo, for
n
en el rango3141592650
de3141592659
,d=10
y el último dígito den
selecciona uno de los otros dígitos. Luego sumamos-d/2
para obtener valores negativos.Alternativa independiente, también 43 bytes:
fuente
len(`n`)
lugar delen(str(n))
.n=2**63-1
ya que la representación seL
agrega (str(n)
abordaría eso por tres bytes si es necesario).Brachylog 2, 11 bytes
Pruébalo en línea!
También probé un algoritmo que usa particiones aditivas en una lista, pero no fue más corto. Este es un generador que produce un flujo infinito de enteros como salida; el enlace TIO tiene un encabezado para imprimir los primeros diez mil de ellos.
Explicación
El programa comienza probando todos los enteros posibles en secuencia (
≜
prueba todas las posibilidades restantes, para enteros por defecto). Eso es 0, 1, -1, 2, -2, etc. (aunque los enteros negativos no llegan al final del programa). Este es el único paso "infinito" del programa; Todos los demás son finitos.~×
luego genera todas las factorizaciones posibles del número entero, trata diferentes órdenes como diferentes y usa solo valores de 2 en adelante (por lo que solo hay muchas); tenga en cuenta que los números compuestos están permitidos en la factorización, no solo primos. Esto significa que todas las secuencias posibles de enteros ≥ 2 serán generadas por este paso en algún momento de la ejecución de la función (como tal, una secuencia necesariamente tiene algún producto, y ese producto se generará en algún punto por la inicial≜
).Luego necesitamos mapear el conjunto de esas secuencias en el conjunto de todas las secuencias de enteros, lo que se realiza en dos pasos: restar 2 (
-₂
) de cada elemento (ᵐ
), dándonos el conjunto de todas las secuencias de enteros no negativos, luego tomando más o menos (~ȧ
es decir, "un valor cuyo valor absoluto es") cada elemento (ᵐ
) El último paso es obviamente no determinista, por lo que Brachylog lo trata como un generador, generando todas las listas posibles cuyos elementos son más o menos el elemento correspondiente de la lista de entrada. Esto significa que ahora tenemos un generador para todas las secuencias enteras posibles, y las genera en un orden que significa que todas se generan (específicamente, el orden que obtienes si tomas el valor absoluto de cada elemento, suma 2 a cada elemento, y luego ordenar por el producto de los elementos resultantes).Desafortunadamente, la pregunta quiere una sola secuencia, no una secuencia de secuencias, por lo que necesitamos dos comandos más. Primero,
≜
solicita a Brachylog que genere explícitamente la secuencia de secuencias estrictamente (en lugar de producir una estructura de datos que describa el concepto de una secuencia generada mediante este método, y no generar las secuencias hasta que sea necesario); Esto sucede para que el programa sea más rápido en este caso y garantiza que la salida se produzca en el orden solicitado. Finalmente,∋
hace que el generador genere los elementos de las secuencias individuales de uno en uno (pasando a la siguiente secuencia una vez que genera todos los elementos de la secuencia anterior).El resultado final: cada posible secuencia entera se genera y genera, un elemento a la vez, y todos se concatenan en una sola secuencia universal.
fuente
Pyth - 11 bytes
n
El producto cartesiano de poder[-n, n]
para todosn
.Pruébelo en línea aquí (finitamente).
fuente
Python 2 ,
10099 bytesitertools
bucle incorporado a indefinidamente.Pruébalo en línea!
Imprime indefinidamente todas las permutaciones del
n
rango entero repetido veces[-n; n)
para todos los enteros no negativosn
.Puede buscar el primer desplazamiento
k
para cualquier subsecuencia utilizando esta versión modificada .fuente
while~0:
. Je je ...itertools.count
Perl 6 , 91 bytes
Pruébalo en línea!
Esto usa un método similar a algunas de las otras respuestas. Utiliza productos cartesianos para imprimir los elementos
(-1,0,1)
, luego todos los pares ordenados de los elementos(-2,-1,0,1,2)
, luego todos los tripletes ordenados de los elementos(-3,-2,-1,0,1,2,3)
, etc.Soy nuevo en Perl, por lo que podría haber más golf que se podría hacer.
Versión más legible:
fuente