Te numery Shotgun to sekwencja o dość prostej definicji, ale jakiejś ciekawej strukturze. Zacznij od liczb naturalnych:

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

Teraz weź wszystkie liczby według wskaźników podzielnych przez 2 , zgrupuj je w pary i zamień liczby w każdej parze:

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

Teraz zrób to samo z indeksami podzielnymi przez 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, ...

A następnie dla 4 , 5 , 6 i tak dalej:

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

Po k takich kroków pierwsze liczby k + 1 zostaną naprawione. Możemy więc zdefiniować nieskończoną sekwencję liczb Strzelby jako granicę pozwalającą k przejść do nieskończoności. Pierwsze 66 liczb to:

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

Ciekawostka: pomimo tego, że uzyskano ją przez permutację liczb naturalnych, sekwencja nie zawiera liczb pierwszych.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą n > 0, znajdź nnumer Strzelby. Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i zwrócić wynik lub wydrukować go do STDOUT (lub najbliższej alternatywy).

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).

Liderów

Otrzymuję więcej odpowiedzi, niż myślałem, a także kilka osób konkurujących w tym samym języku. Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

# 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

Dość naiwna implementacja odpowiedzi na skrypt golfowy @ PeterTaylor .

Wypróbuj online tutaj

Używa tych samych sztuczek, aby przekształcić pętlę while w fold, tak jak robi to inny program Pyth poniżej.

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

Naiwna kopia algorytmu @ Sp3000 przetłumaczona na Pyth.

Możesz spróbować online tutaj

Wykorzystuje redukcję (nazwa pytona dla fold) do emulacji pętli while. Wymienia to, range(input, 2)co działa w Pyth range(2, input)[::-1]. Pozostałe Pyth związane golfs polega na zastosowaniu notzamiast <2i przy użyciu y„s tryb podwojenia wartości argumentów liczbowych ukryte.

> <>, 52 45 bajtów

Strona Esolangs dla> <>

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

Istnieje wiele elementów do kopiowania i przenoszenia, dzięki kilku potrzebnym modułom i mnożeniom. Logika jest dokładnie taka sama jak w moim rozwiązaniu Python .

Pobiera dane wejściowe za pośrednictwem punktu kodowego ze STDIN, np "!" = 33 -> 75.

Python 2, 58 bajtów

i=n=input()
while~-i:n+=(n%i<1)*i*(n/i%2*2-1);i-=1
print n

Podobnie jak większość innych odpowiedzi, pomysł polega na pracy wstecz.

Nazwijmy krok k+1krok i, aby po kroku iwszystkie wielokrotności izostały zamienione. Potrzebujemy dwóch prostych obserwacji:

• Pozycja nw tablicy jest zamieniana tylko na etapie, ijeśli njest podzielna przez i,
• Aby dowiedzieć się, czy jesteś niższą, czy wyższą liczbą w zamianie, spójrz na n/i mod 2. Jeśli jest to 1, jesteś niższą liczbą (i zamienisz się), w przeciwnym razie jesteś wyższą liczbą (i zamienisz się).

To daje nam algorytm do pracy wstecz. Spróbujmy z 6, zaczynając od ostatniego kroku (kroku i = 6):

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

Teraz wiemy, że liczba pochodzi z pozycji 12. Następnie:

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)

Teraz wiemy, że wcześniej pochodziło z 16 lat. Wreszcie:

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)

Ponieważ jest to pierwszy krok (pamiętaj k+1), skończyliśmy, a liczba, która kończy się na pozycji 6, pierwotnie pochodziła z pozycji 14, tj. Szósta liczba strzelb to 14.

A teraz wyjaśnienie w języku 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 bajtów

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

Prawdopodobnie dalsza gra w golfa, szczególnie w pierwszym rzędzie. Definiuje funkcję, sktóra przyjmuje ni zwraca nnumer strzelby.

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]

Wyjaśnienie

Funkcja pomocnika #przyjmuje dwie liczby ni kzwraca kliczbę th z listy zdefiniowanej przez zastosowanie operacji zamiany par na każdą nliczbę. Na przykład zastosowanie go do pierwszych 20 liczb z wynikiem n = 4daje:

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

Wynik s njest uzyskiwany przez zmniejszenie („zwijanie”) listy [2..n]przez funkcję drugiego rzędu (.).(#), która przyjmuje liczbę mi funkcję f(początkowo funkcję tożsamości id), i zwraca funkcję, która przyjmuje ki zwraca f (m # k). Na przykład w przypadku, n = 4gdy lista [2,3,4]jest zredukowana do funkcji, która przyjmuje ki zwraca id (4 # (3 # (2 # k))). idJest potrzebna tylko dla przypadku bazowego n = 1, w którym lista jest pusta. Na koniec przekazujemy tej funkcji dane wejściowe k = n, uzyskując nnumer strzelby.

CJam, 32 bajty

Wystarczy postępować zgodnie ze specyfikacją do rzeczy. Uruchamianie instrukcji na większym zestawie, aby nie wpływać na n- ^tą liczbę.

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

Wypróbuj online tutaj

Rubin, 92 bajty

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

Mój pierwszy golfowy wysiłek. Nie opiera się na żadnej innej odpowiedzi.

Teraz, gdy spojrzałem na niektóre inne, zauważyłem, że większość po prostu definiuje funkcję, a nie kompletny program, który przyjmuje dane wejściowe i generuje dane wyjściowe. OP poprosił o pełny program z wejściem i wyjściem. Czy zwyczajowo ignoruje się takie wymagania?

84 bajtów

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

Po przeanalizowaniu innych odpowiedzi i stwierdzeniu, że możliwe jest iteracyjne rozwiązanie.

Python 2, 97 79 znaków

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)

Określa poprawną wartość dla każdego indeksu, rekurencyjnie ścigając liczbę do tyłu. Algorytm został odkryty niezależnie.

edycja: teraz drukuje tylko nliczbę th zamiast pierwszych nliczb. Oczywiście podejście iteracyjne byłoby krótsze, ale nie chcę kopiować kodu Sp3000.

Haskell, 79 bajtów

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

Zastosowanie: p 66które wyjścia145

Niewiele do wyjaśnienia: funkcja #rekurencyjnie oblicza liczbę strzelby w pozycji ikroku s. p nzwraca liczbę w pozycji nkroku n.

k, 41 bajtów

{{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 i y są domyślnymi 1. i 2. argumentem
• $[b;t;f] operator trójskładnikowy ocenia odpowiednio b, a następnie odpowiednio t / f
• b!a modulo b
• _ piętro, rzutuje wynik podziału na liczbę całkowitą
• % podział
• {...}/[x;y] napełnij {...} znakiem x i zastosuj na liście y, jest równoważne f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
• | rewers
• ! iota, wygeneruj listę od 0 do n-1

Common Lisp, 113 91

(iteracyjnie: 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))))))

(oryginał, rekurencyjny: 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)))))

Przykład

W wersji rekurencyjnej:

(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

Testy

Kontrole i miary dla wersji iteracyjnej:

(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 bajtów

(For[i=n=#,n>1,--n,If[n∣i,i+=Mod[i,2n]2-n]];i)&

Zdecydowałem się na golfa w mojej referencyjnej implementacji. Jest ∣to symbol Unicode dla „dzieli” i liczy 3 bajty. W przeciwnym razie używa tego samego algorytmu, jak wszyscy inni.

Definiuje nienazwaną funkcję, która przyjmuje njako pojedynczy parametr i zwraca nnumer strzelby.

GolfScript, 27 znaków

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

Wyjaśnienie

Jeśli f(i, n)jest to wartość w pozycji npo i-1transformacji, mamy

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

gdzie ^oznacza bitowe xor; dane wejściowe nchcemy obliczyć f(n, n).

Konwersja funkcji rekurencyjnej na pętlę jest nieciekawa; interesujący jest sposób, w jaki

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

można przepisać. Bardziej oczywistym podejściem jest stwierdzenie, że tak musi być

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

dla niektórych g. Oczywiście gzmienia się pomiędzy 1i -1, ponieważ pozycje zamieniają się naprzemiennie w górę i w dół; ponieważ g(1) = 1(ponieważ 1zamienia się na 2) mamy

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

gdzie **oznacza potęgowanie. Ostateczne oszczędności pochodzą z przepisania tego jako

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

Sekcja

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

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

Demo online

Jest to część mojej odpowiedzi w GolfScript , zapożyczając pętlę od odpowiedzi Martina CJam i wykorzystując divmodoperatora CJam . ( Powiedziałem, że to się przyda!).

Julia, 61 57 bajtów

n->(i=n;while~-i!=0 n+=(n%i<1)*i*(n÷i%2*2-1);i-=1;end;n)

Tworzy to nienazwaną funkcję, która przyjmuje pojedynczy argument ni zwraca nnumer strzelby. Aby to nazwać, nadaj mu nazwę, np f=n->(...).

Przykłady:

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

Obecnie jest to oparte na niesamowitej odpowiedzi Pythona na @ Sp3000 . Wrócę do tego wkrótce, ponieważ musi być krótszy sposób na zrobienie tego w Julii niż to, co tutaj zrobiłem. Wszelkie uwagi są mile widziane, jak zawsze.

GML, 76 bajtów

n=argument0;i=n;while~-1{n+=(n mod i<1)*i*(n/i mod 2*2-1)i--}show_message(n)

Informacje o GML

CJam, 28 27 bajtów

Jest to więc trochę zawstydzające ... zanim to opublikowałem, spróbowałem zagrać w golfa i dostałem do 30 bajtów w CJam. Żadna z istniejących odpowiedzi jeszcze tego nie pokonała. W międzyczasie udało mi się również zgolić jeszcze trzy bajty. W komentarzu jest krótsze rozwiązanie Pyth, ale w odpowiedzi nie opublikowano nic krótszego, więc oto jest. Może inspiruje to ludzi APL / J, aby spróbowali nieco bardziej (lub ktoś faktycznie opublikował rozwiązanie Pyth), zanim będę musiał zaakceptować własną odpowiedź. ;)

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

Sprawdź to tutaj.

Wyjaśnienie

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 bajty

   (]+[*(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

Spróbuję zagrać w golfa jeszcze trochę i dodam jakieś wyjaśnienie później.

Wypróbuj online tutaj.

TI-Basic 83/84, 40 bajtów

Input A:For(I,A,2,~1:A+(AfPart(I/2)-1)I(1>IfPart(A/I->A:End:A

Informacje o TI-Basic

Ruby, 57 47 bajtów

Jest to zasadniczo SP3000 roztwór Pythona (z sugestią w XNOR ) przeliczeniu na Ruby. Prawdopodobnie mógłbym zagrać w golfa w kilku miejscach.

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