Shotgun Numbers

><>, 52 45 bytes

Esolangs page for ><>

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.

Takes input via a code point from STDIN, e.g. "!" = 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

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

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 nth 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 kth number in the list defined by applying the pair swap operation to every nth 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 nth shotgun number.