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

function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=0,c=0,p=-1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);t++;c=p==o?c:t;i=i.replace("{{PLACE}}",c+".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);p=o;$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=47338;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>

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.

> <>, 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.

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

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.

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í

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.

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.

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.

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

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

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.

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
}/

CJam, 24 bytes

l~__(,f-{_Imd!~)\#I*-}fI

Demostración en línea

Este es un puerto de mi respuesta GolfScript , tomando prestado el bucle de la respuesta CJam de Martin y explotando el divmodoperador de CJam . ( ¡Dije que sería útil!).

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.

GML, 76 bytes

n=argument0;i=n;while~-1{n+=(n mod i<1)*i*(n/i mod 2*2-1)i--}show_message(n)

Información sobre GML

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.";

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í.

TI-Basic 83/84, 40 bytes

Input A:For(I,A,2,~1:A+(AfPart(I/2)-1)I(1>IfPart(A/I->A:End:A

Información sobre TI-Basic

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}