[Question]
  [
The [Shotgun numbers](https://oeis.org/A064494) are a sequence with a rather simple definition but some interesting structure. Start with the natural numbers:
```
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
```
Now take all numbers at indices divisible by **2**, group them into pairs, and swap the numbers in each pair:
```
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, ...
```
Now do the same with indices divisible by **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, ...
```
And then for **4**, **5**, **6**, and so on:
```
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, ...
...
```
After **k** such steps, the first **k+1** numbers will be fixed. So we can define the infinite sequence of Shotgun numbers as the limit of letting **k** go to infinity. The first 66 numbers are:
```
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, ...
```
**Fun fact:** Despite being obtained by only permuting the natural numbers, this sequence does not contain any primes.
## The Challenge
Given an integer `n > 0`, find the `n`th Shotgun number. You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and return the output or print it to STDOUT (or closest alternative).
This is code golf, so the shortest submission (in bytes) wins.
## Leaderboards
This is getting more answers than I thought, as well as several people competing in the same language. So here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
```
# Language Name, N bytes
```
where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:
```
# 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>
```
  
[Answer]
# ><>, ~~52~~ 45 bytes
[**Esolangs page for ><>**](http://esolangs.org/wiki/Fish)
```
i:&&:&1-?vn;
2*1-*+20.>:&:&%1(&:&*{:}&:1-&,2%
```
There's a lot of copying and moving elements around, thanks to the several modulo and multiplications needed. The logic is exactly the same as my [Python solution](https://codegolf.stackexchange.com/a/47345/21487).
Takes [input via a code point](http://meta.codegolf.stackexchange.com/a/4719/8478) from STDIN, e.g. `"!" = 33 -> 75`.
[Answer]
# Python 2, 58 bytes
```
i=n=input()
while~-i:n+=(n%i<1)*i*(n/i%2*2-1);i-=1
print n
```
Like most of the other answers, the idea is to work backwards.
---
Let's call step `k+1` step `i`, so that on step `i` all the multiples of `i` are swapped. We need two simple observations:
* Position `n` in the array is only swapped at step `i` if `n` is divisible by `i`,
* To tell whether you're the lower number or the higher number in the swap, look at `n/i mod 2`. If this is 1 you're the lower number (and will swap up), otherwise you're the higher number (and will swap down).
This gives us an algorithm for working backwards. Let's try it with 6, starting from the last step (step `i = 6`):
```
Step 6: Position 6 swaps with position 12 (6 is divisible by 6, 6/6 = 1 == 1 mod 2)
```
So now we know the number came from position 12. Then:
```
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)
```
So now we know it came from 16 before that. Finally:
```
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)
```
Since this is the first step (remember, `k+1`), we're done and the number that ends up in position 6 originally came from position 14, i.e. the 6th shotgun number is 14.
So now for the Python explanation:
```
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
```
[Answer]
# 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
```
Probably further golfable, especially the first row. This defines a function `s` that takes `n` and returns the `n`th shotgun number.
```
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]
```
### Explanation
The helper function `#` takes in two numbers `n` and `k`, and returns the `k`th number in the list defined by applying the pair swap operation to every `n`th number. For example, applying it to the first 20 numbers with `n = 4` yields this:
```
map (4#) [1..20]
[1,2,3,8,5,6,7,4,9,10,11,16,13,14,15,12,17,18,19,24]
```
The result of `s n` is obtained by reducing ("folding") the list `[2..n]` by the second-order function `(.).(#)`, which takes in a number `m` and a function `f` (initially the identity function `id`), and returns a function that takes `k` and returns `f (m # k)`. For example, in the case `n = 4` the list `[2,3,4]` is reduced to a function that takes `k` and returns `id (4 # (3 # (2 # k)))`. The `id` is only needed for the base case `n = 1`, where the list is empty. Finally, we give this function the input `k = n`, obtaining the `n`th shotgun number.
[Answer]
# CJam, 32 bytes
Just following the spec to the point. Running the instructions on a larger set so as to not affect the nth number.
```
ri:N)2#,:)N{))/2/{:)~\@}%:+}/N(=
```
[Try it online here](http://cjam.aditsu.net/#code=ri%3AN)2%23%2C%3A)N%7B))%2F2%2F%7B%3A)~%5C%40%7D%25%3A%2B%7D%2FN(%3D&input=4)
[Answer]
# Pyth, 19 ~~22~~
```
u-G*H^_!%GH/GHrhQ2Q
```
A fairly naive implementation of [@PeterTaylor's golfscript answer](https://codegolf.stackexchange.com/a/47630/31625).
[Try it online here](https://pyth.herokuapp.com/?code=u-G*H%5E_!%25GH%2FGHrhQ2Q&input=100)
This uses the same tricks to convert a while loop into a fold as the other Pyth program below does.
---
```
u+G**H!%GHty%/GH2rhQ2Q
```
A naive copy of [@Sp3000's](https://codegolf.stackexchange.com/a/47345/31625) algorithm translated to Pyth.
[You can try it online here](https://pyth.herokuapp.com/?code=u%2BG**H!%25GHty%25%2FGH2rhQ2Q&input=5)
Uses reduce (python's name for fold) to emulate the while loop. It enumerates over the `range(input, 2)` which in Pyth works out to `range(2, input)[::-1]`. The other Pyth-related golfs involves using `not` instead of `<2` and using `y`'s hidden mode of doubling the value of numeric arguments.
[Answer]
# 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
```
My first code golf effort. Not based on any other answer.
---
Now that I've looked at some of the others though, I notice that most just define a function, not a complete program that accepts input and produces output. The OP asked for a complete program with input and output. Is it customary to ignore such requirements?
---
# 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
```
After looking at other answers and realizing that an iterative solution is possible.
[Answer]
# Python 2, ~~97~~ 79 chars
```
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)
```
It determines for each index the correct value by recursively chasing the number backwards. 
The algorithm was independent discovered. 
edit: Now it only prints the `n`th number instead of the first `n` numbers. Of course an iterative approach would be shorter, but I don't want to copy Sp3000's code. 
[Answer]
# 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
```
Usage: `p 66` which outputs `145`
Not much to explain: The function `#` recursively calculates the shotgun number at position `i` of step `s`. `p n` returns the number at position `n` of step `n`.
[Answer]
## 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 and y are the implicit 1st and 2nd argument
* `$[b;t;f]` ternary operator, evaluates b followed by t/f respectively
* `b!a` a modulo b
* `_` floor, casts the result of the division to an int
* `%` division
* `{...}/[x;y]` prime {...} with x and apply over the list y, is equivalent to f[f[..f[f[x;y0];y1];..yn-1];yn]
* `|` reverse
* `!` iota function, generate list 0 through n-1
[Answer]
# Common Lisp, ~~113~~ 91
(iterative: 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, recursive: 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)))))
```
## Example
With the recursive version:
```
(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
```
## Tests
Checks and measures for iterative version:
```
(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
```
[Answer]
# Mathematica, ~~53~~ 49 bytes
```
(For[i=n=#,n>1,--n,If[n∣i,i+=Mod[i,2n]2-n]];i)&
```
I decided to golf my reference implementation. The `∣` is the Unicode symbol for "divides", and counts for 3 bytes. Otherwise, this uses the same algorithm as everyone else.
It defines an unnamed function which takes `n` as a single parameter and returns the `n`th Shotgun number.
[Answer]
## GolfScript, 27 chars
```
~.,(~%{):i\.@%!~)1$i/?i*-}/
```
### Explanation
If `f(i, n)` is the value at position `n` after `i-1` transformations, we have
```
f(1, n) = n
f(i, n) = f(i - 1, n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n)  for i > 1
```
where `^` denotes bitwise xor; given input `n`, we want to compute `f(n, n)`.
The conversion from a recursive function to a loop is uninteresting; what is interesting is the way in which
```
n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n
```
can be rewritten. The more obvious approach is to say that it must be
```
n + (n % i == 0 ? i : 0) * g(n / i)
```
for some `g`. Obviously `g` alternates between `1` and `-1`, as the positions swap alternately up and down; since `g(1) = 1` (because `1` swaps up to `2`), we have
```
n + (n % i == 0 ? i : 0) * -1**(1 + n / i)
```
where `**` denotes exponentiation. The final savings come from rewriting this as
```
n - i * (n % i == 0 ? -1 : 0)**(n / i)
```
### Dissection
```
~             # 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
}/
```
[Answer]
## CJam, 24 bytes
```
l~__(,f-{_Imd!~)\#I*-}fI
```
[Online demo](http://cjam.aditsu.net/#code=l~__(%2Cf-%7B_Imd!~)%5C%23I*-%7DfI&input=11)
This is a port of [my GolfScript answer](https://codegolf.stackexchange.com/a/47630/194), borrowing the loop from [Martin's CJam answer](https://codegolf.stackexchange.com/a/47623/194) and exploiting CJam's `divmod` operator. ([I said](https://codegolf.stackexchange.com/a/16987/194) it would be useful!).
[Answer]
# Julia, ~~61~~ 57 bytes
```
n->(i=n;while~-i!=0 n+=(n%i<1)*i*(n÷i%2*2-1);i-=1;end;n)
```
This creates an unnamed function which takes a single argument `n` and returns the `n`th shotgun number. To call it, give it a name, e.g. `f=n->(...)`.
Examples:
```
julia> for i = 1:10 println(f(i)) end
1
4
8
6
12
14
16
9
18
20
```
Currently this is based on @Sp3000's awesome [Python answer](https://codegolf.stackexchange.com/a/47345/20469). I'll revisit this soon because there must be a shorter way to do this in Julia than what I've done here. Any input is welcome, as always.
[Answer]
# 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)
```
[Information about GML](http://en.wikipedia.org/wiki/GameMaker:_Studio#Scripting)
[Answer]
# CJam, ~~28~~ 27 byte
So this is slightly embarrassing... before posting this, I tried golfing this myself and got to 30 bytes in CJam. None of the existing answers have beaten that yet. In the meantime I also managed to shave off three more bytes. There *is* a shorter Pyth solution in a comment, but nothing shorter has been posted in an answer, so here it is. Maybe it inspires the APL/J people to try a bit harder (or someone actually post the Pyth solution), before I have to accept my own answer. ;)
```
l~__(,f-{_I_+%_+I-_zI=*+}fI
```
[Test it here.](http://cjam.aditsu.net/#code=l~__(%2Cf-%7B_I_%2B%25_%2BI-_zI%3D*%2B%7DfI&input=100)
## Explanation
```
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.";
```
[Answer]
# 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
```
Will try to golf it a bit more and add some explanation later.
[Try it online here.](http://tryj.tk/)
[Answer]
# 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
```
[Information about TI-Basic](http://tibasicdev.wikidot.com/home)
[Answer]
# Ruby, ~~57~~ 47 bytes
This is essentially [Sp3000](https://codegolf.stackexchange.com/users/21487/sp3000)'s Python solution (with [xnor's suggestion](https://chat.stackexchange.com/transcript/message/20478433#20478433)) translated to Ruby. I could probably golf it down in a few places though.
```
->n{n.downto(2).map{|i|n+=i*(n/i%2-~-n/i%2)};n}
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 13 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
╠¼│σ╣Gp☺πΩ■φ├
```
[Run and debug it](https://staxlang.xyz/#p=ccacb3e5b9477001e3eafeedc3&i=1%0A2%0A3%0A4%0A5%0A6&m=2)
Same idea as Peter Taylor's answer, and almost the same code.
]