Números de escopeta

45

Los números de escopeta son una secuencia con una definición bastante simple pero con una estructura interesante. Comience con los números naturales:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

Ahora tome todos los números en índices divisibles por 2 , agrúpelos en pares e intercambie los números en cada par:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
   ^     ^     ^     ^      ^       ^       ^  
    <--->       <--->        <----->         <----
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...

Ahora haz lo mismo con los índices divisibles por 3 :

1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
      ^        ^        ^           ^          
       <------>          <--------->           
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...

Y luego para 4 , 5 , 6 , y así sucesivamente:

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

Después de k tales pasos, los primeros k + 1 números serán corregidos. Entonces podemos definir la secuencia infinita de números de escopeta como el límite de dejar que k vaya al infinito. Los primeros 66 números son:

1, 4, 8, 6, 12, 14, 16, 9, 18, 20, 24, 26, 28, 22, 39, 15, 36, 35, 40, 38, 57, 34, 48, 49, 51, 44,
46, 33, 60, 77, 64, 32, 75, 56, 81, 68, 76, 58, 100, 55, 84, 111, 88, 62, 125, 70, 96, 91, 98, 95,
134, 72, 108, 82, 141, 80, 140, 92, 120, 156, 124, 94, 121, 52, 152, 145, ...

Dato curioso: a pesar de haberse obtenido al permutar solo los números naturales, esta secuencia no contiene ningún primo.

El reto

Dado un número entero n > 0, encuentra el nnúmero de escopeta th. Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y devolver el resultado o imprimirlo en STDOUT (o la alternativa más cercana).

Este es el código de golf, por lo que gana el envío más corto (en bytes).

Tablas de clasificación

Esto está obteniendo más respuestas de lo que pensaba, así como varias personas que compiten en el mismo idioma. Así que aquí hay un Fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Martin Ender
fuente
1
Ese hecho divertido es una locura, ¿este algoritmo baraja todos los números primos hasta el final? ¿O hay otros números naturales que tampoco ocurrirán?
Devon Parsons
1
@DevonParsons Sí, baraja todos los números primos "hasta el final". Pero creo que también faltan otros números. Parece que 10, 21, 25y 30no aparecen ya sea, por ejemplo.
Martin Ender
3
Esto suena como una pregunta del Proyecto Euler. No creo que lo sea ... pero tal vez debería serlo.
Corey Ogburn
99
En general, en la kiteración th, el kelemento th en la matriz se transpone a la 2kposición th, y no se volverá a tocar hasta la 2kiteración th, momento en el que se transpone a la 4kposición th, hasta el infinito. Un primo no se transpone hasta que llega su turno, por así decirlo, por lo que todos los primos se barajan hacia adelante. Pero podemos hacer fácilmente una lista de las víctimas inocentes simplemente imprimiendo el primer elemento que se transpondrá en la iteración 2 y cada iteración impar. La lista va: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ...
Théophile
3
@ Sherlock9 Hecho! Si se aprueba, será https://oeis.org/A266679 . ¡Feliz año nuevo!
Théophile el

Respuestas:

5

Pyth, 19 22

u-G*H^_!%GH/GHrhQ2Q

Una implementación bastante ingenua de la respuesta de golfscript de @ PeterTaylor .

Pruébalo en línea aquí

Utiliza los mismos trucos para convertir un bucle while en un pliegue como lo hace el otro programa Pyth a continuación.


u+G**H!%GHty%/GH2rhQ2Q

Una copia ingenua del algoritmo de @ Sp3000 traducido a Pyth.

Puedes probarlo en línea aquí.

Utiliza reduce (nombre de python para pliegue) para emular el ciclo while. Enumera sobre lo range(input, 2)que en Pyth funciona range(2, input)[::-1]. Los otros campos de golf relacionados con Pyth implica el uso noten lugar de <2y el uso de y'S modo de duplicar el valor de argumentos numéricos oculta.

FryAmTheEggman
fuente
21

> <>, 52 45 bytes

Página de Esolangs para> <>

i:&&:&1-?vn;
2*1-*+20.>:&:&%1(&:&*{:}&:1-&,2%

Hay muchos elementos de copia y movimiento, gracias a los diversos módulos y multiplicaciones necesarios. La lógica es exactamente la misma que mi solución Python .

Toma entrada a través de un punto de código de STDIN, por ejemplo "!" = 33 -> 75.

Sp3000
fuente
10
Y recibió el premio por el formato de entrada más incómodo: P
Caridorc
+1 de todos modos, no te preocupes :)
Caridorc
@ Sp3000 IMO solo debería contar como uno
SuperJedi224
@ SuperJedi224 En realidad, según esta meta publicación aparentemente -vcuenta como tres: /
Sp3000
17

Python 2, 58 bytes

i=n=input()
while~-i:n+=(n%i<1)*i*(n/i%2*2-1);i-=1
print n

Como la mayoría de las otras respuestas, la idea es trabajar al revés.


Llamemos paso a k+1paso i, para que en el paso se intercambien itodos los múltiplos de i. Necesitamos dos observaciones simples:

  • La posición nen la matriz solo se intercambia en el paso isi nes divisible por i,
  • Para saber si eres el número más bajo o el número más alto en el intercambio, mira n/i mod 2. Si este es 1, usted es el número más bajo (y cambiará hacia arriba), de lo contrario, es el número más alto (y cambiará hacia abajo).

Esto nos da un algoritmo para trabajar hacia atrás. Probémoslo con 6, comenzando desde el último paso (paso i = 6):

Step 6: Position 6 swaps with position 12 (6 is divisible by 6, 6/6 = 1 == 1 mod 2)

Entonces ahora sabemos que el número vino de la posición 12. Luego:

Step 5: No swap (12 not divisible by 5)
Step 4: Position 12 swaps with position 16 (12 is divisible by 4, 12/4 = 3 == 1 mod 2)

Así que ahora sabemos que vino de 16 antes de eso. Finalmente:

Step 3: No swap (16 not divisible by 3)
Step 2: Position 16 swaps with position 14 (16 divisible by 2, 16/2 = 8 == 0 mod 2)

Como este es el primer paso (recuerde k+1), hemos terminado y el número que termina en la posición 6 vino originalmente de la posición 14, es decir, el sexto número de escopeta es 14.

Así que ahora para la explicación de Python:

i=n=input()             Read input, and store into i (step) and n (position)
while~-i:               while i-1 != 0:, or since we're descending with i this is just while i>1:
  n+=                   Add to the current position...
    (n%i<1)*            1* whatever's next if n is divisible by i, otherwise 0* (i.e. nothing)
    i*                  How many positions n might go up/down
    (n/i%2*2-1)         n/i%2 tell us higher/lower, *2-1 maps 0 or 1 to -1 (down) or +1 (up)
  i-=1                  Decrement the step number
print n                 Output
Sp3000
fuente
forma interesante de escribir i-1como~-i
mbomb007
66
@ mbomb007: De acuerdo. Sin embargo, es inteligente, ya que tiene el mismo significado pero elimina la necesidad de un espacio después while. Buen trabajo, Sp3000.
Alex A.
Lo más breve que pude obtener esto en Pyth fue mediante el uso de reducir:u+G**H!%GHty%/GH2rhQ2Q
FryAmTheEggman
1
@FryAmTheEggman, Sp3000, ¿ninguno de ustedes va a publicar eso?
Martin Ender
@ MartinBüttner Originalmente no lo publiqué porque sentí que era demasiado copia. Lo publicaré como respuesta de CW por ahora.
FryAmTheEggman
6

Haskell, 68 bytes

n#k|mod k(2*n)<1=k-n|mod k n<1=k+n|k>0=k
s n=foldr((.).(#))id[2..n]n

Probablemente más golfable, especialmente la primera fila. Esto define una función sque toma ny devuelve el nnúmero de escopeta th.

map s [1..66]
[1,4,8,6,12,14,16,9,18,20,24,26,28,22,39,15,36,35,40,38,57,34,48,49,51,44,46,33,60,77,64,32,75,56,81,68,76,58,100,55,84,111,88,62,125,70,96,91,98,95,134,72,108,82,141,80,140,92,120,156,124,94,121,52,152,145]

Explicación

La función auxiliar #toma dos números ny k, y devuelve el knúmero th en la lista definida aplicando la operación de intercambio de pares a cada nnúmero th. Por ejemplo, aplicándolo a los primeros 20 números con n = 4rendimientos esto:

map (4#) [1..20]
[1,2,3,8,5,6,7,4,9,10,11,16,13,14,15,12,17,18,19,24]

El resultado de s nse obtiene al reducir ("plegar") la lista [2..n]por la función de segundo orden (.).(#), que toma un número my una función f(inicialmente la función de identidad id), y devuelve una función que toma ky devuelve f (m # k). Por ejemplo, en el caso, n = 4la lista [2,3,4]se reduce a una función que toma ky devuelve id (4 # (3 # (2 # k))). La idúnica que se necesita para el caso base n = 1, donde la lista está vacía. Finalmente, le damos entrada a esta función k = n, obteniendo el nnúmero de escopeta th.

Zgarb
fuente
6

CJam, 32 bytes

Simplemente siguiendo las especificaciones hasta el punto. Ejecutar las instrucciones en un conjunto más grande para no afectar el enésimo número.

ri:N)2#,:)N{))/2/{:)~\@}%:+}/N(=

Pruébalo en línea aquí

Optimizador
fuente
5

Ruby, 92 bytes

def s(d,n)
d==1?n:s(d-1,n%d==0?n+(n%(d*2)==0?-d :d):n)
end
n=ARGV[0].to_i
print s(n,n).to_s

Mi primer esfuerzo de código de golf. No se basa en ninguna otra respuesta.


Ahora que he visto algunos de los otros, noto que la mayoría simplemente define una función, no un programa completo que acepta entrada y produce salida. El OP solicitó un programa completo con entrada y salida. ¿Es costumbre ignorar tales requisitos?


84 bytes

n=ARGV[0].to_i
d=n
while d>1
n+=(n%d==0?(n%(d*2)==0?-d :d):0)
d-=1
end
print n.to_s

Después de mirar otras respuestas y darse cuenta de que es posible una solución iterativa.

Salomón lento
fuente
2
Algunas mejoras para su solución de 84 bytes: 1. Cambie ARGVa la $*magia global. 2. El to_ses innecesario. 3. En lugar de asignar da nuna línea separada, simplemente hazlo d=n=...para eliminar un carácter. ¡Buen trabajo para tu primer golf! :)
Pomo de la puerta
1
¿Dónde solicito un programa completo? "Puede escribir un programa o función ...";) (Este también es el valor predeterminado para los desafíos de código de golf , pero generalmente lo incluyo para completarlo).
Martin Ender
Para agregar a las sugerencias de @ Doorknob, dos conjuntos de corchetes en la n+=línea son innecesarios, y ambas ocurrencias ==0pueden cambiarse de manera segura <1.
Peter Taylor
5

Python 2, 97 79 caracteres

g=lambda n,k:n>1and g(n-1,k-(k%n<1)*n*(-1)**(k/n%2))or k
n=input()
print g(n,n)

Determina para cada índice el valor correcto persiguiendo recursivamente el número hacia atrás. El algoritmo fue descubierto de forma independiente.

editar: ahora solo imprime el nnúmero th en lugar de los primeros nnúmeros. Por supuesto, un enfoque iterativo sería más corto, pero no quiero copiar el código de Sp3000.

Jakube
fuente
Sí, creo que todos convergerán en esto. Aunque la g(i,i)parte me pareció particularmente molesta ...
Sp3000
2
El lenguaje debe estar marcado como Python 2, debido a la printdeclaración.
mbomb007
@ mbomb007 Lo corrigió.
Jakube
4

Haskell, 79 bytes

1#i=i
s#i|i`mod`(2*s)==0=(s-1)#(i-s)|i`mod`s==0=(s-1)#(i+s)|1<2=(s-1)#i
p n=n#n

Uso: p 66que salidas145

No hay mucho que explicar: la función #calcula recursivamente el número de escopeta en la posición idel paso s. p ndevuelve el número en la posición ndel paso n.

nimi
fuente
Oh, no vi tu respuesta antes de enviar la mía. Parece que tenemos enfoques bastante diferentes.
Zgarb
4

k, 41 bytes

{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}

 / apply to an int
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]} 42
111
 / apply to 1 through 66
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}'1+!66
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44 46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95 134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145
  • {...} lambda, x e y son el primer y segundo argumento implícito
  • $[b;t;f] operador ternario, evalúa b seguido de t / f respectivamente
  • b!a a módulo b
  • _ piso, arroja el resultado de la división a un int
  • % división
  • {...}/[x;y] imprima {...} con x y aplique sobre la lista y, es equivalente a f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
  • | marcha atrás
  • ! función iota, genera la lista de 0 a n-1
mollmerx
fuente
4

Lisp común, 113 91

(iterativo: 91)

(defun s(n)(do((r n(1- r)))((= r 1)n)(if(= 0(mod n r))(incf n(* r(if(oddp(/ n r))1 -1))))))

(original, recursivo: 113)

(defun s(n &optional(r n))(cond((= r 1)n)((= 0(mod n r))(s(+ n(* r(if(oddp(/ n r))1 -1)))(1- r)))(t(s n(1- r)))))

Ejemplo

Con la versión recursiva:

(trace s)
(s 10)

  0: (S 10)
    1: (S 20 9)
      2: (S 20 8)
        3: (S 20 7)
          4: (S 20 6)
            5: (S 20 5)
              6: (S 15 4)
                7: (S 15 3)
                  8: (S 18 2)
                    9: (S 20 1)
                    9: S returned 20
         ...
    1: S returned 20
  0: S returned 20

Pruebas

Verificaciones y medidas para la versión iterativa:

(let ((list '(1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44
              46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95
              134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145)))
  (time
   (loop for r in list
         for n from 1
         always (= r (s n)))))

 => T

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  807,160 processor cycles
  32,768 bytes consed
volcado de memoria
fuente
4

Mathematica, 53 49 bytes

(For[i=n=#,n>1,--n,If[n∣i,i+=Mod[i,2n]2-n]];i)&

Decidí jugar golf a mi implementación de referencia. El es el símbolo Unicode para "divide", y cuenta para 3 bytes. De lo contrario, esto usa el mismo algoritmo que todos los demás.

Define una función sin nombre que toma ncomo parámetro único y devuelve el nnúmero de escopeta.

Martin Ender
fuente
4

GolfScript, 27 caracteres

~.,(~%{):i\.@%!~)1$i/?i*-}/

Explicación

Si f(i, n)es el valor en la posición ndespués de las i-1transformaciones, tenemos

f(1, n) = n
f(i, n) = f(i - 1, n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n)  for i > 1

donde ^denota bitor xor; dada entrada n, queremos calcular f(n, n).

La conversión de una función recursiva a un ciclo no es interesante; lo interesante es la forma en que

n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n

puede ser reescrito El enfoque más obvio es decir que debe ser

n + (n % i == 0 ? i : 0) * g(n / i)

para algunos g. Obviamente galterna entre 1y -1, a medida que las posiciones cambian alternativamente hacia arriba y hacia abajo; desde g(1) = 1(porque 1intercambia hasta 2), tenemos

n + (n % i == 0 ? i : 0) * -1**(1 + n / i)

donde **denota exponenciación. Los ahorros finales provienen de reescribir esto como

n - i * (n % i == 0 ? -1 : 0)**(n / i)

Disección

~             # Evaluate input to get n
.,(~%{        # For n-1 downto 1...
  ):i         #   Let i be that value + 1, so for i = n downto 2...
  \.@%!       #   Find n % i == 0 ? 1 : 0
  ~)          #   Negate
  1$i/?       #   Raise to the power of n/i
  i*-         #   Multiply by i and subtract
}/
Peter Taylor
fuente
Ya que tiene las respuestas GS y CJam más cortas, ¿por qué no también tiene la respuesta Pyth más corta? u-G*H^_!%GH/GHrhQ2QSi no desea publicar esto usted mismo, dígame / agréguelo a la respuesta de CW.
FryAmTheEggman
@FryAmTheEggman, puede que no sea muy practicado en CJam, pero al menos puedo leerlo más o menos. No tengo ni idea de lo que dice Pyth en su comentario, aunque por contexto supongo que es un puerto de esta respuesta. Por lo tanto, es mejor que lo publique, porque puede responder preguntas al respecto.
Peter Taylor
4

Julia, 61 57 bytes

n->(i=n;while~-i!=0 n+=(n%i<1)*i*(n÷i%2*2-1);i-=1;end;n)

Esto crea una función sin nombre que toma un solo argumento ny devuelve el nnúmero de escopeta th. Para llamarlo, dale un nombre, por ejemplo f=n->(...).

Ejemplos:

julia> for i = 1:10 println(f(i)) end
1
4
8
6
12
14
16
9
18
20

Actualmente esto se basa en la increíble respuesta de Python de @ Sp3000 . Revisaré esto pronto porque debe haber una forma más corta de hacer esto en Julia que lo que he hecho aquí. Cualquier aportación es bienvenida, como siempre.

Alex A.
fuente
3

CJam, 28 27 bytes

Así que esto es un poco vergonzoso ... antes de publicar esto, intenté jugar al golf y llegué a 30 bytes en CJam. Ninguna de las respuestas existentes ha superado eso todavía. Mientras tanto, también logré eliminar tres bytes más. No es una solución más corto Pyth en un comentario, pero nada más corto ha sido publicado en una respuesta, así que aquí está. Tal vez inspire a las personas de APL / J a esforzarse un poco más (o alguien realmente publique la solución Pyth), antes de que tenga que aceptar mi propia respuesta. ;)

l~__(,f-{_I_+%_+I-_zI=*+}fI

Pruébalo aquí.

Explicación

l~                          "Read input N and eval.";
  __(,                      "Duplicate twice, create range [0 1 2 ... N-2].";
      f-                    "Subtract each from N, giving [N N-1 N-2 ... 2].";
        {               }fI "For each element, storing the element in I.";
         _I_+%_+I-          "Compute 2(N % 2I)-I - the shuffling offset";
                  _zI=      "Check that this offset is ±I.";
                      *+    "Multiply the offset by this boolean and update to N.";
Martin Ender
fuente
3

J, 34 32 bytes

   (]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)

   ((]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)) every 1+i.20  NB. running with inputs 1..20
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38

Intentaré jugar al golf un poco más y agregaré alguna explicación más adelante.

Pruébelo en línea aquí.

randomra
fuente
1

Ruby, 57 47 bytes

Esto es esencialmente SP3000 solución Python 's (con la sugerencia de XNOR ) traducida a Ruby. Sin embargo, probablemente podría jugar golf en algunos lugares.

->n{n.downto(2).map{|i|n+=i*(n/i%2-~-n/i%2)};n}
Sherlock9
fuente