Die Schrotflinten-Nummern sind eine Sequenz mit einer ziemlich einfachen Definition, aber einer interessanten Struktur. Beginnen Sie mit den natürlichen Zahlen:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
Nehmen Sie nun alle Zahlen bei durch 2 teilbaren Indizes , gruppieren Sie sie in Paare und tauschen Sie die Zahlen in jedem Paar aus:
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, ...
Machen Sie jetzt dasselbe mit Indizes, die durch 3 teilbar sind :
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, ...
Und dann für 4 , 5 , 6 und so weiter:
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, ...
...
Nach k solchen Schritten werden die ersten k + 1 Zahlen festgelegt. Wir können also die unendliche Folge von Schrotflinten-Zahlen als die Grenze definieren, bis zu der k gegen unendlich gehen darf . Die ersten 66 Zahlen sind:
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, ...
Unterhaltsame Tatsache: Obwohl diese Sequenz nur durch Permutieren der natürlichen Zahlen erhalten wird, enthält sie keine Primzahlen.
Die Herausforderung
Ermitteln Sie bei einer Ganzzahl n > 0
die n
Nummer der Schrotflinte. Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und die Ausgabe zurückgeben oder an STDOUT (oder die nächstgelegene Alternative) ausgeben.
Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes).
Bestenlisten
Das gibt mehr Antworten, als ich dachte, und es treten mehrere Personen in derselben Sprache gegeneinander an. Hier ist also ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.
Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:
# Language Name, N bytes
Wo N
ist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:
# Ruby, <s>104</s> <s>101</s> 96 bytes
quelle
10
,21
,25
und30
erscheint auch nicht, zum Beispiel.k
dritten Iteration dask
dritte Element im Array in die2k
dritte Position transponiert und erst bei der2k
dritten Iteration wieder berührt , wenn es in die4k
dritte Position unendlich transponiert wird . Ein Prim wird erst transponiert, wenn er sozusagen an der Reihe ist, und alle Primzahlen werden vorwärts gemischt. Aber wir können leicht eine Liste der unschuldigen Opfer erstellen, indem wir einfach das erste Element ausdrucken, das bei Iteration 2 und jeder ungeraden Iteration transponiert werden soll. Die Liste lautet: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ...Antworten:
Pyth, 19
22Eine ziemlich naive Implementierung von @ PeterTaylors Golfscript-Antwort .
Probieren Sie es hier online aus
Dies verwendet die gleichen Tricks, um eine while-Schleife in eine Falte umzuwandeln wie das andere Pyth-Programm unten.
Eine naive Kopie des in Pyth übersetzten @ Sp3000- Algorithmus.
Sie können es hier online ausprobieren
Verwendet reduct (Pythons Name für fold), um die while-Schleife zu emulieren. Es zählt über das auf,
range(input, 2)
was in Pyth klapptrange(2, input)[::-1]
. Bei den anderen Pyth-bezogenen Golfspielen wirdnot
anstelle von<2
und unter Verwendungy
des versteckten Modus der Wertverdopplung von numerischen Argumenten verwendet.quelle
> <>,
5245 BytesEsolangs Seite für> <>
Durch die verschiedenen erforderlichen Module und Multiplikationen werden viele Elemente kopiert und verschoben. Die Logik entspricht genau meiner Python-Lösung .
Nimmt Eingang über einen Codepunkt von STDIN, zB
"!" = 33 -> 75
.quelle
-v
drei: /Python 2, 58 Bytes
Wie bei den meisten anderen Antworten geht es darum, rückwärts zu arbeiten.
Nennen wir step
k+1
stepi
, damit bei stepi
alle Vielfachen voni
getauscht werden. Wir brauchen zwei einfache Beobachtungen:n
im Array wird nur bei Schritt getauscht,i
wenn diesn
durch teilbari
ist.n/i mod 2
. Wenn dies 1 ist, sind Sie die niedrigere Nummer (und werden nach oben tauschen), andernfalls sind Sie die höhere Nummer (und werden nach unten tauschen).Dies gibt uns einen Algorithmus zum Rückwärtsarbeiten. Versuchen wir es mit 6, beginnend mit dem letzten Schritt (Schritt
i = 6
):Jetzt wissen wir also, dass die Nummer von Position 12 kam. Dann:
Jetzt wissen wir also, dass es von 16 vorher gekommen ist. Endlich:
Da dies der erste Schritt ist (denken Sie daran,
k+1
), sind wir fertig und die Nummer, die auf Position 6 landet, stammt ursprünglich von Position 14, dh die 6. Schrotflintennummer ist 14.Nun zur Python-Erklärung:
quelle
i-1
als~-i
while
. Gute Arbeit, Sp3000.u+G**H!%GHty%/GH2rhQ2Q
Haskell, 68 Bytes
Wahrscheinlich weiter golfbar, vor allem die erste Reihe. Dies definiert eine Funktion
s
, dien
dien
Nummer der Schrotflinte annimmt und zurückgibt .Erläuterung
Die Hilfsfunktion
#
nimmt zwei Zahlenn
und aufk
und gibt diek
th-Zahl in der Liste zurück, die durch Anwenden der Paartauschoperation auf jeden
th-Zahl definiert wird. Wenn Sie es beispielsweise auf die ersten 20 Zahlen anwenden, erhalten Sien = 4
Folgendes:Das Ergebnis von
s n
wird durch Reduzieren ("Falten") der Liste[2..n]
durch die Funktion zweiter Ordnung erhalten(.).(#)
, die eine Zahlm
und eine Funktionf
(anfangs die Identitätsfunktionid
) aufnimmtk
und eine Funktion zurückgibt, die nimmt und zurückgibtf (m # k)
. In diesem Fall wirdn = 4
die Liste[2,3,4]
beispielsweise auf eine Funktion reduziert, die dauertk
und zurückgibtid (4 # (3 # (2 # k)))
. Dasid
wird nur für den Basisfall benötigtn = 1
, bei dem die Liste leer ist. Schließlich geben wir dieser Funktion die Eingabek = n
und erhalten dien
Nummer der Schrotflinte.quelle
CJam, 32 Bytes
Folgen Sie einfach der Spezifikation auf den Punkt. Ausführen der Anweisungen auf einem größeren Satz, um die n- te Zahl nicht zu beeinflussen .
Probieren Sie es hier online aus
quelle
Ruby, 92 Bytes
Meine erste Code Golf Anstrengung. Keine andere Antwort.
Nun, da ich mir einige der anderen angeschaut habe, stelle ich fest, dass die meisten nur eine Funktion definieren, kein vollständiges Programm, das Eingaben akzeptiert und Ausgaben erzeugt. Das OP forderte ein vollständiges Programm mit Ein- und Ausgängen. Ist es üblich, solche Anforderungen zu ignorieren?
84 Bytes
Nachdem Sie sich andere Antworten angesehen und erkannt haben, dass eine iterative Lösung möglich ist.
quelle
ARGV
zum$*
Magic Global. 2. Dasto_s
ist unnötig. 3. Anstattd
inn
einer separaten Zeiled=n=...
zuzuweisen, müssen Sie nur einen Buchstaben abschneiden. Gute Arbeit für dein erstes Golfspiel! :)n+=
Zeile nicht erforderlich, und beide Vorkommen von==0
können sicher in geändert werden<1
.Python 2,
9779 ZeichenSie ermittelt für jeden Index den richtigen Wert, indem sie die Zahl rekursiv rückwärts jagt. Der Algorithmus wurde eigenständig entdeckt.
edit: Jetzt wird nur noch die
n
th Nummer anstatt der erstenn
Nummern gedruckt . Ein iterativer Ansatz wäre natürlich kürzer, aber ich möchte den Code von Sp3000 nicht kopieren.quelle
g(i,i)
Teil allerdings besonders ärgerlich ...print
Anweisung als Python 2 markiert werden .Haskell, 79 Bytes
Verwendung:
p 66
welche Ausgänge145
Nicht viel zu erklären: Die Funktion
#
berechnet rekursiv die Schrotflintenanzahl ani
der Schrittpositions
.p n
Gibt die Nummer an der Positionn
von step zurückn
.quelle
k, 41 Bytes
{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}
{...}
Lambda, x und y sind das implizite 1. und 2. Argument$[b;t;f]
ternärer Operator, bewertet b, gefolgt von t / fb!a
ein Modulo b_
Boden, wirft das Ergebnis der Teilung zu einem int%
Einteilung{...}/[x;y]
{...} mit x beginnen und über die Liste y anwenden, entspricht f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]|
umkehren!
iota-Funktion, generiere Liste 0 bis n-1quelle
Common Lisp,
11391(iterativ: 91)
(original, rekursiv: 113)
Beispiel
Mit der rekursiven Version:
Tests
Überprüft und misst die iterative Version:
quelle
Mathematica,
5349 BytesIch entschied mich für meine Referenzimplementierung. Das
∣
ist das Unicode-Symbol für "Divides" und zählt für 3 Bytes. Andernfalls wird derselbe Algorithmus wie für alle anderen verwendet.Es definiert eine unbenannte Funktion, die
n
einen einzelnen Parameter annimmt und dien
Nummer der Schrotflinte zurückgibt .quelle
GolfScript, 27 Zeichen
Erläuterung
Wenn
f(i, n)
ist der Wert an der Positionn
nachi-1
Transformationen, haben wirwo
^
bezeichnet bitweises xor; gegebene Eingaben
wollen wir berechnenf(n, n)
.Die Konvertierung von einer rekursiven Funktion in eine Schleife ist uninteressant. Interessant ist die Art und Weise, in der
kann umgeschrieben werden. Der naheliegendere Ansatz ist zu sagen, dass es sein muss
für manche
g
. Offensichtlichg
wechselt zwischen1
und-1
, während die Positionen abwechselnd auf und ab wechseln; dag(1) = 1
(weil1
tauscht2
) haben wirwo
**
Exponentiation bezeichnet. Die endgültigen Einsparungen ergeben sich aus der Umschreibung alsPräparation
quelle
u-G*H^_!%GH/GHrhQ2Q
Wenn Sie dies nicht selbst posten möchten, teilen Sie es mir mit / fügen Sie es der CW-Antwort hinzu.CJam, 24 Bytes
Online-Demo
Dies ist eine Portierung meiner GolfScript-Antwort , die die Schleife von Martins CJam-Antwort entlehnt und den CJam-
divmod
Operator ausnutzt . ( Ich sagte, es wäre nützlich!).quelle
Julia,
6157 BytesDadurch wird eine unbenannte Funktion erstellt, die ein einzelnes Argument verwendet
n
und dien
Nummer der Schrotflinte zurückgibt . Um es zu nennen, geben Sie ihm einen Namen, zf=n->(...)
.Beispiele:
Derzeit basiert dies auf der großartigen Python-Antwort von @ Sp3000 . Ich werde das bald wiederholen, denn es muss einen kürzeren Weg geben, dies in Julia zu tun als das, was ich hier getan habe. Jede Eingabe ist wie immer willkommen.
quelle
GML, 76 Bytes
Informationen zu GML
quelle
CJam,
2827 ByteDas ist also etwas peinlich ... bevor ich das gepostet habe, habe ich es selbst versucht und bin in CJam auf 30 Bytes gekommen. Keine der vorhandenen Antworten hat das bisher geschlagen. In der Zwischenzeit habe ich auch noch drei Bytes gespart. Es gibt eine kürzere Pyth-Lösung in einem Kommentar, aber in einer Antwort wurde nichts Kürzeres gepostet. Vielleicht inspiriert es die APL / J-Leute, sich etwas mehr anzustrengen (oder jemand, der die Pyth-Lösung tatsächlich veröffentlicht), bevor ich meine eigene Antwort akzeptieren muss. ;)
Teste es hier.
Erläuterung
quelle
J,
3432 BytesIch werde versuchen, ein bisschen mehr Golf zu spielen und später eine Erklärung hinzufügen.
Probieren Sie es hier online aus.
quelle
TI-Basic 83/84, 40 Bytes
Informationen zu TI-Basic
quelle
Ruby,
5747 BytesDies ist im Wesentlichen die Python-Lösung von Sp3000 (mit dem Vorschlag von xnor ), die in Ruby übersetzt wurde. Ich könnte es aber wahrscheinlich an einigen Stellen spielen.
quelle