Shotgun Numbers

Question

The Shotgun numbers 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 nth 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 1

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

Answer 2

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 3

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.

Answer 4

CJam, 32 bytes

Just following the spec to the point. Running the instructions on a larger set so as to not affect the n^th number.

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

Try it online here

Answer 5

Pyth, 19 22

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

A fairly naive implementation of @PeterTaylor's golfscript answer.

Try it online here

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 algorithm translated to Pyth.

You can try it online here

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 6

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 7

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 nth 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 8

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 9

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 10

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 11

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 nth Shotgun number.

Answer 12

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 13

CJam, 24 bytes

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

Online demo

This is a port of my GolfScript answer, borrowing the loop from Martin's CJam answer and exploiting CJam's divmod operator. (I said it would be useful!).

Answer 14

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 nth 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. 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 15

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

Answer 16

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.

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 17

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.

Answer 18

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

Answer 19

Ruby, 57 47 bytes

This is essentially Sp3000's Python solution (with xnor's suggestion) 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 20

Stax, 13 bytes

╠¼│σ╣Gp☺πΩ■φ├

Run and debug it

Same idea as Peter Taylor's answer, and almost the same code.