Os números da espingarda são uma sequência com uma definição bastante simples, mas com alguma estrutura interessante. Comece com os números naturais:

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

Agora pegue todos os números nos índices divisíveis por 2 , agrupe-os em pares e troque os números em 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, ...

Agora faça o mesmo com índices divisíveis 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, ...

E depois para 4 , 5 , 6 e assim por diante:

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

Após k tais etapas, os primeiros números k + 1 serão corrigidos. Assim, podemos definir a sequência infinita de números de espingarda como o limite de deixar k ir ao infinito. Os primeiros 66 números são:

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

Curiosidade: apesar de ter sido obtida permutando apenas os números naturais, essa sequência não contém números primos.

O desafio

Dado um número inteiro n > 0, encontre o nnúmero da espingarda. Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e retornar a saída ou imprimi-la em STDOUT (ou alternativa mais próxima).

Isso é código de golfe, então a submissão mais curta (em bytes) vence.

Classificação

Isso está recebendo mais respostas do que eu pensava, além de várias pessoas competindo no mesmo idioma. Então, aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

# 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

Uma implementação bastante ingênua da resposta do golfscript de @ PeterTaylor .

Experimente online aqui

Isso usa os mesmos truques para converter um loop while em uma dobra, como o outro programa Pyth abaixo.

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

Uma cópia ingênua do algoritmo do @ Sp3000 traduzida para Pyth.

Você pode experimentá-lo online aqui

Usa reduzir (o nome do python para fold) para emular o loop while. Ele enumera sobre o range(input, 2)que em Pyth funciona range(2, input)[::-1]. Os outros campos de golfe relacionadas com Pyth envolve o uso notem vez de <2e usando y's modo de dobrar o valor de argumentos numéricos escondido.

> <>, 52 45 bytes

Página Esolangs para> <>

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

Existem muitos elementos de cópia e movimentação, graças aos vários módulos e multiplicações necessárias. A lógica é exatamente a mesma da minha solução Python .

Recebe entrada através de um ponto de código de STDIN, por exemplo "!" = 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 a maioria das outras respostas, a idéia é trabalhar para trás.

Vamos chamar step k+1step i, para que no step itodos os múltiplos de isejam trocados. Precisamos de duas observações simples:

• A posição nna matriz é trocada apenas na etapa ise né divisível por i,
• Para saber se você é o número mais baixo ou o maior na troca, veja n/i mod 2. Se este for 1, você é o número mais baixo (e será trocado), caso contrário, você é o número mais alto (e será trocado).

Isso nos dá um algoritmo para trabalhar de trás para frente. Vamos tentar com 6, começando na última etapa (etapa i = 6):

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

Então agora sabemos que o número veio da posição 12. Então:

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)

Então agora sabemos que veio dos 16 antes disso. 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 é o primeiro passo (lembre-se k+1), terminamos e o número que termina na posição 6 veio originalmente da posição 14, ou seja, o sexto número da espingarda é 14.

Então agora a explicação do 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

Provavelmente ainda mais jogável, especialmente a primeira linha. Isso define uma função sque pega ne retorna o nnúmero da espingarda.

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]

Explicação

A função auxiliar #recebe dois números ne k, e retorna o knúmero th na lista definida aplicando a operação de troca de pares a cada nnúmero th. Por exemplo, aplicá-lo aos 20 primeiros números com n = 4isso:

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

O resultado de s né obtido reduzindo ("dobrando") a lista [2..n]pela função de segunda ordem (.).(#), que recebe um número me uma função f(inicialmente a função de identidade id) e retorna uma função que recebe ke retorna f (m # k). Por exemplo, no caso, n = 4a lista [2,3,4]é reduzida a uma função que recebe ke retorna id (4 # (3 # (2 # k))). A idsó é necessário para o caso de base n = 1, em que a lista está vazia. Finalmente, damos a esta função a entrada k = n, obtendo o nnúmero da espingarda.

CJam, 32 bytes

Apenas seguindo as especificações ao ponto. Executando as instruções em um conjunto maior para não afetar o ^enésimo número.

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

Experimente online aqui

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

Meu primeiro esforço de golfe com código. Não se baseia em nenhuma outra resposta.

Agora que já observei algumas outras, percebo que a maioria apenas define uma função, não um programa completo que aceita entrada e produz saída. O OP solicitou um programa completo com entrada e saída. É habitual ignorar esses 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

Depois de examinar outras respostas e perceber que é possível uma solução 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)

Ele determina para cada índice o valor correto, perseguindo recursivamente o número. O algoritmo foi descoberto independentemente.

editar: Agora, apenas imprime o nnúmero th em vez dos primeiros nnúmeros. É claro que uma abordagem iterativa seria mais curta, mas não quero copiar o código do 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 66quais saídas145

Não há muito a explicar: a função #calcula recursivamente o número da espingarda na posição ido passo s. p nretorna o número na posição nda etapa 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, xey são o primeiro e o segundo argumentos implícitos
• $[b;t;f] operador ternário, avalia b seguido de t / f, respectivamente
• b!a a módulo b
• _ chão, lança o resultado da divisão para um int
• % divisão
• {...}/[x;y] prime {...} com x e aplique sobre a lista y, é equivalente a f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
• | marcha ré
• ! função iota, gere a lista de 0 a n-1

Lisp comum, 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, recursiva: 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)))))

Exemplo

Com a versão 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

Testes

Verificações e medidas para a versão 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)&

Eu decidi jogar golfe minha implementação de referência. O ∣é o símbolo Unicode para "divide" e conta com 3 bytes. Caso contrário, isso usa o mesmo algoritmo que todos os outros.

Ele define uma função sem nome que recebe ncomo único parâmetro e retorna o nnúmero da espingarda.

GolfScript, 27 caracteres

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

Explicação

Se f(i, n)é o valor na posição napós as i-1transformações, temos

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

onde ^denota xor bit a bit; dada entrada n, queremos calcular f(n, n).

A conversão de uma função recursiva para um loop é desinteressante; o que é interessante é a maneira pela qual

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

pode ser reescrito. A abordagem mais óbvia é dizer que deve ser

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

para alguns g. Obviamente galterna entre 1e -1, à medida que as posições se alternam alternadamente para cima e para baixo; desde g(1) = 1(porque 1muda até 2), temos

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

onde **denota exponenciação. A economia final vem da reescrita como

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

Dissecação

~             # 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

Demonstração online

Esta é uma porta da minha resposta GolfScript , pegando emprestado o loop da resposta CJam de Martin e explorando o divmodoperador da CJam . ( Eu disse que seria ú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)

Isso cria uma função sem nome, que recebe um único argumento ne retorna o nnúmero da espingarda. Para chamá-lo, dê um nome, por exemplo f=n->(...).

Exemplos:

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

Atualmente, isso se baseia na incrível resposta em Python do @ Sp3000 . Vou revisitar isso em breve, porque deve haver uma maneira mais curta de fazer isso em Julia do que o que eu fiz aqui. Qualquer entrada é bem-vinda, como sempre.

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)

Informações sobre GML

CJam, 28 27 bytes

Portanto, isso é um pouco embaraçoso ... antes de postar isso, tentei jogar sozinho e cheguei a 30 bytes no CJam. Nenhuma das respostas existentes superou isso ainda. Enquanto isso, também consegui raspar mais três bytes. Não é uma solução mais curto Pyth em um comentário, mas nada mais curto foi postado em uma resposta, por isso aqui está. Talvez inspire o pessoal da APL / J a se esforçar um pouco mais (ou alguém realmente postar a solução Pyth), antes que eu tenha que aceitar minha própria resposta. ;)

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

Teste aqui.

Explicação

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

Vai tentar jogar um pouco mais e adicionar algumas explicações mais tarde.

Experimente online aqui.

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

Informações sobre o TI-Basic

Ruby, 57 47 bytes

Esta é essencialmente a solução Python do Sp3000 (com sugestão do xnor ) traduzida para Ruby. Eu provavelmente poderia jogar golfe em alguns lugares.

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