La secuencia de salto

19

Considere la siguiente secuencia:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Parece bastante sin patrón, ¿verdad? Así es como funciona. Comenzando con 0, saltar nnúmeros enteros, ncomenzando en 1. Ese es el siguiente número en la secuencia. Luego, agregue cualquier número "omitido" y que aún no se haya visto en orden ascendente. Luego, incremente ny salte desde el último número agregado. Repite este patrón.

Entonces, por ejemplo, cuando llegamos 11, estamos en n=5. Incrementamos npara ser n=6, saltar hacia arriba y 17luego agregar, 13 14 15 16ya que aún no se han visto. Nuestro próximo salto es n=7, entonces el siguiente elemento en la secuencia es 23.

El reto

Dada la entrada x, da salida al xtérmino de esta secuencia, los primeros xtérminos de la secuencia, o construye una lista infinita de los términos de la secuencia. Puede elegir 0 o 1 indexación.

E / S y reglas

La entrada y salida se pueden dar por cualquier método conveniente .
Se puede suponer que la entrada y la salida encajan en el tipo de número nativo de su idioma.
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).

code-golf sequence AdmBorkBork
fuente

Aparentemente no está (¿todavía?) En OEIS

JayCe

@ JayCe No estoy sorprendido, es una secuencia bastante arbitraria.

AdmBorkBork

Respuestas:

24

JavaScript (ES7), 41 bytes

Devuelve el enésimo término de la secuencia, indexado en 0.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Pruébalo en línea!

¿Cómo?

Caso principal: $n > 3$

Los primeros cuatro términos de la secuencia son especiales, así que dejémoslos a un lado por ahora.

Para , la secuencia se ve así: $n > 3$

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

Podemos notar que, de hecho, hay dos subsecuencias intercaladas:

La mayoría de los valores pertenecen a la subsecuencia para la que simplemente tenemos: $A$

$A (n) = n - 1$ $A(n) = n - 1$
Algunos otros valores pertenecen a la subsecuencia (resaltada con paréntesis en el diagrama anterior) cuyos índices siguen la secuencia aritmética 3, 3, 4, 6, 9, 13, 18, 24 ... y para los cuales tenemos: $B$

$B (n, k) = n + k - 1$ $B(n,k) = n + k - 1$
donde es el índice en la secuencia principal y es el índice en la sub-secuencia de . $n$ $k$ $B$

Los índices de en la secuencia principal están dados por: $B$

n_{k} = \frac{k^{2} - k + 6}{2}

$n_k = \frac{k^2 - k + 6}{2}$

Dado , sabemos que el término correspondiente en la secuencia principal pertenece a si es una solución entera de la ecuación cuadrática: $n$ $B$ $n$

x^{2} - x + 6 - 2 n = 0

$x^2 - x + 6 - 2n = 0$

cuyo discriminante es:

Δ = 1 - 4 (6 - 2 n) = 8 n - 23

$\Delta = 1 - 4(6 - 2n) = 8n - 23$

y cuya solución positiva es:

x = \frac{1 + \sqrt{Δ}}{2}

$x = \frac{1 + \sqrt{\Delta}}{2}$

Esperamos que sea un número entero. De ahí la prueba: $\sqrt{\Delta}$

(d = (n-- * 8 - 23) ** .5) % 1

Casos especiales: $0 \le n \le 3$

Para , el discriminante es negativo y su raíz cuadrada resulta en NaN . Para , el discriminante es . Por lo tanto, se consideran estos cuatro primeros términos de la secuencia de pertenecer a la sub-secuencia de . $n < 3$ $n = 3$ $1$ $B$

Si aplicamos nuestra fórmula estándar n - ~ d / 2 , obtendríamos:

- \frac{1}{2}, \frac{1}{2}, \frac{3}{2}, 3

$-\frac 1 2, \frac 1 2, \frac 3 2, 3$

en lugar de:

0, 1, 3, 2

$0, 1, 3, 2$

Es por eso que XOR estos resultados con respectivamente. $0,1,2\text{ and }1$

Arnauld
fuente

10

Casco , 12 bytes

Θṁṙ_1C+ḣ2tNN

Pruébalo en línea!

Salidas como una lista infinita. Aquí es una versión que imprime la primera N .

Explicación

Θṁṙ_1C + ḣ2tNN - Programa completo. No tiene entrada, sale a STDOUT.
         tN: construye la lista infinita de números naturales, comenzando desde 2.
      + ḣ2 - Y añádele [1, 2]. Rendimientos [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Corta la lista infinita de enteros positivos en partes de esos
               Tamaños. Rendimientos [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 ṁ - Mapa y aplanar los resultados a partir de entonces.
  ṙ_1: gire cada uno hacia la derecha 1 unidad.
               Rendimientos [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - Anteponer un 0. Rendimientos [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]

Sr. Xcoder
fuente

7

Haskell , 43 bytes

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

Pruébalo en línea!

Define una lista infinita:

  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …

Lynn
fuente

4

Jalea , 15 bytes

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

Este es un programa completo que, dado n , imprime los primeros n elementos de la secuencia.

Pruébalo en línea!

Cómo funciona

0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.


+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.

Dennis
fuente

3

C (gcc), 73 67 64 bytes

t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

Pruébalo en línea!

Define una función fque toma 0 indexado ny produce el nnúmero th en la secuencia.

Podemos analizar la secuencia de la siguiente manera:

f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

Primero manejamos la sección central:

for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

Tenga en cuenta que los argumentos de la izquierda (4, 6, 9, 13, ...) siguen un patrón: primero agregue dos, luego agregue tres, luego agregue cuatro, y así sucesivamente. Comenzamos en t=4y agregamos d(que comienza en 2) cada iteración del ciclo, incrementando den el proceso.

El cuerpo del bucle es más interesante. Recuerde que queremos mapear 4 a 5, 6 a 8, 9 a 12, etc .; eso es solo agregar d-1si xes t. Sin embargo, esta lógica viene antes del último caso, f(n) = n - 1por lo que sabemos que vamos a restar 1 al final. Por lo tanto, simplemente podemos agregar dif x == t( x-t||(x+=d)). Sin embargo, también necesitaremos para salir del bucle inmediatamente después de esto - así que agregamos que para dconseguir la absurda buscando d+=x+=d, que siempre hará que la d<xcondición de falla.

Esto cubre todo excepto los primeros cuatro valores. Mirándolos en binario, obtenemos:

00 -> 00
01 -> 01
10 -> 11
11 -> 10

Entonces, queremos voltear el último bit si 2 <= x < 4. Esto se logra con x^x/2. x/2da el segundo bit menos significativo, por lo que XORing esto con el número original voltea el último bit si el número es 2 o 3.

Pomo de la puerta
fuente

3

Jalea , 13 10 bytes

-3 Gracias a Dennis (use la indexación 0 para guardar 2 de la configuración de suma acumulativa y una disminución final)

Ḷ»2Äi+_>2$

Un enlace monádico que acepta un entero, n indexado en 0 , que devuelve un entero, a (n)

Pruébalo en línea! O ver un conjunto de pruebas

Jonathan Allan
fuente

¡Agradable! Tenía ḶÄ+3i+’, pero no tengo idea de cómo manejar los casos extremos.

Dennis

También tengo Ḷ»ạ¥3para Ḋ3,2;- parece que debería haber terser para este bit.

Jonathan Allan

Ḷ»2Äi+_>2$ahorra 3 bytes, con indexación basada en 0.

Dennis

¡Oh, increíble golf! Estaba atrapado en tierra de 1 índice.

Jonathan Allan

2

Perl 5 con `-pl`70 bytes

$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

Pruébalo en línea!

Dom Hastings
fuente

2

MATL , 22 bytes

1y:"t0)@+h5M:yX-h]qw:)

Emite los primeros ntérminos de la secuencia.

Pruébalo en línea!

Explicación

1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display

Luis Mendo
fuente

Me gusta la carita al final, ahora quiero que todos mis programas MATL terminen con una sonrisa. :)

sundar - Restablecer Monica

@sundar Sí, estoy feliz de que sea un idioma relativamente común en MATL :-D

Luis Mendo

2

Haskell , 51 bytes

0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

Pruébalo en línea!

Un poco más largo que la respuesta de Lynn Haskell , pero el enfoque diferente podría ser interesante, no obstante.

Laikoni
fuente

1

Ruby , 73 bytes

f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

Pruébalo en línea!

Función recursiva que devuelve los primeros x números de la lista.

crashoz
fuente

1

QBasic, 58 bytes

DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

Salidas indefinidamente. Es posible que desee agregar un SLEEP 1dentro del bucle o hacerlo LOOP WHILE b<100o algo así para ver los resultados.

Básicamente, esto solo implementa la especificación. Observe que los números a los que volvemos siempre serán los números entre el número saltado más recientemente y el número saltado antes de eso. Así que almacenamos estos límites como ay by usamos un FORbucle para imprimir todos los números entre ellos.

DLosc
fuente

1

05AB1E , 14 bytes

0)sƒ¤N+LÁ«}Ùs£

Pruébalo en línea!

Emigna
fuente

1

R , 70 bytes

function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

Pruébalo en línea!

1 indexado
-4 bytes usando Fconstante gracias a la sugerencia de @JAD
-5 bytes invirtiendo la lista gracias a la sugerencia de @Giuseppe
-2 bytes eliminando llaves inútiles para el bucle gracias a la sugerencia de @JAD
-2 bytes usando en setdifflugar dex[x %in% y]

Versión anterior (79 bytes)

digEmAll
fuente

2

79 bytes

JAD

@JAD: Siempre olvidé usar F / T ... No puedo evitarlo, estoy demasiado inclinado a evitar el "código inseguro": D

digEmAll

1

¡La construcción de la lista en reversa guarda 5 bytesy causa un montón de advertencias!

Giuseppe

Ni siquiera es inseguro si F/Tno se redefine en la definición de la función. No (IIRC) modifica el valor global paraF/T

JAD

1

72 bytes

JAD

1

Python 2 , 123 bytes

def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s

Pruébalo en línea!

Dada la entrada x, genera los primeros x términos de la secuencia,

Estoy aprendiendo Python y estos desafíos hacen que las cosas sean más interesantes.

Editar: afeitar algunos espacios en blanco

Diente medio
fuente

Bienvenido a PPCG! Usted puede deshacerse de algunos espacios más en for n in range(1,z) if len(s) < z]; return s: for n in range(1,z)if len(s)<z];return s.

Laikoni

0

Jalea , 16 bytes

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

Pruébalo en línea!

Un byte más largo que la respuesta de Jelly existente, pero esto posiblemente podría jugarse un poco. RÄṬŻk²Ḋ$tal vez podría ser más corto.

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Más largo pero diferente.

dylnan
fuente

0

Ruby , 63 bytes

->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

Pruébalo en línea!

0 indexado. Probablemente se pueda jugar golf.

Restablecer a Monica - notmaynard
fuente

0

Perl 6 , 52 bytes

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

Pruébalo en línea!

Esta es una expresión generadora que usa el ...operador. Busca huecos en la secuencia anterior a @_través de ((^max @_)∖@_).min.?key:

      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

El ?es necesario para el valor inicial que no tiene a .key. Si no se encuentran huecos, agrega n (aquí en la $variable) al último valor de la lista, más uno para 0 errores.

Phil H
fuente

0

Python 3 , 104 bytes

def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

Pruébalo en línea!

Dada la entrada x, genera las primeras x "secuencias"

frosqh
fuente