La secuencia es demasiado meta.

25

Comenzamos con una secuencia en blanco de 1 índice:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

En el enésimo paso, rellenamos cada a (n) espacios en blanco con los enteros mayores que 1 comenzando en el primer espacio en blanco restante, donde a (n) es la enésima entrada de la secuencia.

Después del primer paso:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Tenga en cuenta que a (1) tiene que ser 2 porque el primer entero mayor que 1 es 2.

En el segundo paso, completamos cada a (2) espacios en blanco. Será evidente que a (2) debe ser 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

En el tercer paso, completamos cada a (3) espacios en blanco. De la secuencia, a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

En el cuarto paso, completamos cada a (4) espacios en blanco. De la secuencia, a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Finalmente:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Tarea

Dado n, devuelve el enésimo elemento de la secuencia.

Los primeros 10,000,000 términos de la secuencia se pueden encontrar aquí .

Este es el código de golf . La respuesta más corta en bytes gana. Se aplican lagunas estándar .

code-golf sequence Monja permeable
fuente
@LuisMendo Gracias, lo he agregado.
Leaky Nun
Por curiosidad, ¿qué mal hizo el Sr. Uno para ser excluido de la secuencia?
Dead Possum
@DeadPossum, si completa todos los espacios en blanco, entonces habrá terminado en un solo paso.
Leaky Nun
2
@DeadPossum Si un (n) es 1, entonces el enésimo paso completará cada espacio en blanco restante, terminando la generación.
Leaky Nun
1
@ QBrute proporcioné una lista de los primeros 10,000,000 vinculados en la pregunta; solo complétalos.
Leaky Nun

Respuestas:

20

Haskell , 80 67 bytes

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Pruébalo en línea!

Haskell es el lenguaje perfecto para definir una lista infinita en términos de sí mismo.

Anders Kaseorg
fuente
1
Dado que el enlace TIO funciona como se esperaba, creo que mi pregunta debería ser: ¿Podría agregar una explicación de cómo funciona?
Julian Wolf
2
@JulianWolf Parece que no estás familiarizado con los letguardias de patrones. pattern1 | let pattern2 = expr2 = expr1significa lo mismo que pattern1 = let pattern2 = expr2 in expr1(por la misma razón que [expr1 | let pattern2 = expr2]significa lo mismo que [let pattern2 = expr2 in expr1]).
Anders Kaseorg
1
¡Tengo que recordar a los letguardias de patrones (especialmente que pueden hacer funciones)! Además, m=2:2:2`drop`g mes un byte más corto.
Ørjan Johansen
1
(!!)$0:mes dos bytes más corto.
Ørjan Johansen
1
En realidad, puedes dejar las 2:2:cosas por completo con un poco más de pereza: g ~(a:b)|...y m=g m.
Ørjan Johansen
10

C, 123 bytes

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Pruébalo en línea!

Tutorial

f(n){int*p=calloc(n,4),

Asigne una matriz de n enteros para almacenar los primeros n elementos de la secuencia. Este hardcodes sizeof(int)como 4, lo cual es una suposición segura en la mayoría de los casos y ciertamente estoy dispuesto a hacer en el contexto del golf de código. :)

i=0,j,k;

Todos estos son contadores: ipara el índice del paso en el que estamos, jrecorrer la secuencia buscando espacios vacíos y kcontar cuántos espacios vacíos se han visto.

for(*p=p[1]=2;i<n;++i)

Antes de comenzar nuestro ciclo principal, introducimos a escondidas una inicialización de los dos primeros elementos de la secuencia 2. ( p[0]= *(p + 0)= *p.) Sin kembargo, esto descarta la cuenta , pero ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... también hacemos una inicialización disimulada de k, que prueba para ver si ies menor 2y corrige el valor inicial de ksi es así. El ciclo interno también comienza aquí, que itera sobre toda la secuencia hasta el momento durante cada paso.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Esta línea realmente podría usar algunas explicaciones. Podemos expandir esto a:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

por cortocircuito, y luego por las leyes de De Morgan y el hecho de que 0es falso en C:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

Esto esencialmente dice: "si este espacio está vacío, incremente k. Y si kanteriormente era un múltiplo del tamaño del paso, ejecute la siguiente instrucción". Por lo tanto, ejecutamos la declaración en cada elemento de tamaño de paso , que es exactamente cómo se describe la secuencia. La declaración en sí es simple; lo único que hace es generar 2, 3, 4, ....

n=p[n-1];}

Utilizando el complicado retorno-sin-retorno que trabaja con gcc, nos "retorno" el último elemento de los primeros n términos de la secuencia, que pasa a ser el n º plazo.

Pomo de la puerta
fuente
3

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Pruébalo en línea

Cómo funciona

En lugar de perder el tiempo con las listas, esto usa una fórmula recursiva simple.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))
Anders Kaseorg
fuente
3

Haskell , 67 bytes

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Pruébalo en línea!

Una solución aritmética recursiva que resultó básicamente el mismo método que la respuesta Pyth de Anders Kaseorg .

Este código está cubierto de verrugas, partes feas que parecen que podrían ser eliminadas, pero no vi cómo.

La función i%jrealmente quiere usar un protector para verificar si mod i(f j)>0y evaluar una de las dos expresiones correspondientes. Pero, ambas expresiones usan div i(f j). Unir eso en un guardia no hará que se aplique a ambos lados. Hasta donde yo sé, no se puede hacer que un guardia se "distribuya" sobre otros guardias. lety whereson demasiado largos Entonces, el código usalast para elegir una de dos expresiones mientras el protector vincula la variable. Ugh

Idealmente usaríamos divMod porque se tanto el divy mod, pero (d,m)<-divMod ...es una expresión larga. En su lugar, verificamos de forma hackea que el mod no sea cero al ver si el divvalor multiplicado por el divisor no alcanza el valor original.

El 0%j=2caso no sería necesario si Haskell hiciera un cortocircuito div 0, lo cual no es así. Los .predconvierte la entrada 1-indexada a cero-indexados, o de lo contrario no habría-1 correcciones en todas partes.

xnor
fuente
Si activa %1 indexado, entonces necesita una corrección de cinco bytes, lo que simplemente vincula. Sin embargo , puede fingresar %en línea sin costo, y luego se fconvierte en anónimo, de modo que ahorra dos bytes en general.
Ørjan Johansen
@ ØrjanJohansen ¿Qué quiere decir aquí con en línea? No veo cómo cambiar las referencias fsin perder bytes.
xnor
divModparece ser un byte más barato, ya que permite la ramificación con !!(0^m). Hasta ahora tengo:1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);(%1)
Ørjan Johansen
Como puede ver, la alineación presupone la reindexación 1, que elimina la .pred.
Ørjan Johansen
2

JavaScript (ES6), 98 93 91 bytes

Una función recursiva que se detiene tan pronto como el resultado esté disponible.

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Versión alternativa, 90 bytes.

Sugerido por Shaggy para -1 byte

Este debe ser llamado con f(n)(). Aunque la publicación correspondiente en meta actualmente da una puntuación positiva, esta sintaxis aparentemente está en disputa.

n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Manifestación

Mostrar fragmento de código

Arnauld
fuente
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k?c:++v:(i=1,v=2),i=0,k=a[p]||2))debería funcionar para 92 bytes. Llámalo con f(n)().
Shaggy
@ Shaggy Gracias! Agregado como una versión alternativa.
Arnauld
1

Java 8, 124 bytes

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Expresión lambda.

Crea una matriz de enteros y la llena continuamente hasta que se rellena el enésimo valor.

Predeclarar variables en la parte superior para reducir tantas declaraciones como sea posible ya que cada una intcuesta 4 bytes de espacio en lugar de sumar,n cuál es 2.

En la j'th iteración de cálculo, el número de' espacios en blanco 'que uno debe omitir es igual a a[j](o 2, si está en blanco). Resulta que si el primer espacio en blanco que tenemos que llenar está en la posición k, k * a[j]nos da el 'paso' ( s).

Xanderhall
fuente