# Shotgun Numbers

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.

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>

• That fun fact is crazy, this algorithm shuffles all the primes to the end? Or are there other natural numbers that also will not occur? – Devon Parsons Mar 4 '15 at 13:39
• @DevonParsons Yes it shuffles all primes "to the end". But I think there are other numbers missing as well. It looks like 10, 21, 25 and 30 don't appear either, for example. – Martin Ender Mar 4 '15 at 13:41
• This sounds like a Project Euler question. I don't think it is... but maybe it should be. – Corey Ogburn Mar 4 '15 at 23:27
• In general, at the kth iteration, the kth element in the array gets transposed to the 2kth position, and won't get touched again until the 2kth iteration, at which time it gets transposed to the 4kth position, ad infinitum. A prime doesn't get transposed until its turn comes along, so to speak, so all primes get shuffled forward. But we can easily make a list of the innocent victims simply by printing off the first element to be transposed at iteration 2 and each odd iteration. The list goes: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ... – Théophile Mar 5 '15 at 13:34
• @Sherlock9 Done! If approved, it will be https://oeis.org/A266679. Happy new year! – Théophile Jan 2 '16 at 18:54

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

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

• And you got the award for the most awkward input format ever :P – Caridorc Mar 4 '15 at 14:31
• +1 anyway, don't worry :) – Caridorc Mar 4 '15 at 14:34
• @Sp3000 IMO it should only count as one – SuperJedi224 Dec 31 '15 at 14:41
• @SuperJedi224 Actually, according to this meta post apparently -v counts as three :/ – Sp3000 Jan 3 '16 at 10:34

# 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

• interesting way to write i-1 as ~-i – mbomb007 Mar 4 '15 at 15:05
• @mbomb007: Agreed. Clever though, as it has the same meaning but eliminates the need for a space after while. Nice work, Sp3000. – Alex A. Mar 4 '15 at 15:23
• Shortest I could get this in pyth was by using reduce: u+G**H!%GHty%/GH2rhQ2Q – FryAmTheEggman Mar 4 '15 at 16:45
• @FryAmTheEggman, Sp3000, is neither of you going to post that? – Martin Ender Mar 11 '15 at 0:55
• @MartinBüttner I didn't originally post it as I felt it was too much of a copy. I'll post it as a CW answer for now. – FryAmTheEggman Mar 11 '15 at 13:57

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

# 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

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

• A few improvements for your 84 byte solution: 1. Change ARGV to the $* magic global. 2. The to_s is unnecessary. 3. Instead of assigning d to n on a separate line, just do d=n=... to shave off a character. Nice work for your first golf! :) – Doorknob Mar 5 '15 at 3:47 • Where am I asking for a complete program? "You may write a program or function..." ;) (This is also the default for code-golf challenges, but I usually include it for completeness.) – Martin Ender Mar 5 '15 at 11:39 • To add to @Doorknob's suggestions, two sets of brackets on the n+= line are unnecessary, and both occurrences of ==0 can safely be changed to <1. – Peter Taylor Mar 11 '15 at 14:06 # 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. • Yeah, I think everybody will converge on this. I found the g(i,i) part particularly annoying though... – Sp3000 Mar 4 '15 at 14:51 • The language should be marked as Python 2, because of the print statement. – mbomb007 Mar 4 '15 at 15:04 • @mbomb007 Corrected it. – Jakube Mar 4 '15 at 18:36 # Haskell, 79 bytes 1#i=i s#i|imod(2*s)==0=(s-1)#(i-s)|imods==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. • Oh, I didn't see your answer before submitting mine. Seems like we have quite different approaches. – Zgarb Mar 4 '15 at 16:02 ## 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

# 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


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

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

• Seeing as you have the shortest GS and CJam answers, why not also have the shortest Pyth answer? u-G*H^_!%GH/GHrhQ2Q If you don't want to post this yourself, tell me/add it to the CW answer. – FryAmTheEggman Mar 11 '15 at 15:56
• @FryAmTheEggman, I may not be very practised at CJam, but I can at least more-or-less read it. I haven't a clue what the Pyth in your comment says, although from context I presume it's a port of this answer. So it's best that you post it, because you can answer questions about it. – Peter Taylor Mar 11 '15 at 16:15

## 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!).

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

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


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


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

# 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


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