Numéros de fusil de chasse

45

Les numéros de fusil de chasse sont une séquence avec une définition assez simple mais une structure intéressante. Commencez avec les nombres naturels:

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

Maintenant, prenez tous les nombres aux indices divisibles par 2 , regroupez-les en paires et échangez les nombres de chaque paire:

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

Faites maintenant la même chose avec les indices divisibles par 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, ...

Et puis pour 4 , 5 , 6 et ainsi de suite:

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

Après k ces étapes, les k + 1 premiers nombres seront fixés. Ainsi, nous pouvons définir la séquence infinie de nombres Shotgun comme la limite permettant à k d’ aller à l’infini. Les 66 premiers numéros sont:

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

Fait amusant: bien qu'elle n'ait été obtenue qu'en permutant les nombres naturels, cette séquence ne contient aucun nombre premier.

Le défi

À partir d’un nombre entier n > 0, trouvez le nnuméro du fusil de chasse. Vous pouvez écrire un programme ou une fonction en prenant une entrée via STDIN (ou l’alternative la plus proche), un argument de ligne de commande ou une argumentation de fonction, puis renvoyer la sortie ou l’imprimer sur STDOUT (ou l’alternative la plus proche).

C'est le code de golf, donc la soumission la plus courte (en octets) gagne.

Classements

Cela donne plus de réponses que je ne le pensais, ainsi que plusieurs personnes en compétition dans la même langue. Voici donc un extrait de pile permettant de générer à la fois un classement régulier et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse apparaît, commencez votre réponse par un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores en les effaçant. Par exemple:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Martin Ender
la source
1
Ce fait amusant est fou, cet algorithme mélange tous les nombres premiers jusqu'à la fin? Ou existe-t-il d'autres nombres naturels qui ne se produiront pas non plus?
Devon Parsons
1
@DevonParsons Oui, il mélange tous les nombres premiers "jusqu'à la fin". Mais je pense qu'il manque d'autres chiffres également. Il ressemble 10, 21, 25et 30ne semble pas non plus , par exemple.
Martin Ender
3
Cela ressemble à une question du projet Euler. Je ne pense pas que ce soit ... mais peut-être que cela devrait l'être.
Corey Ogburn
9
En général, à la ktroisième itération, le kdixième élément du tableau est transposé à la 2kdixième position et ne sera pas touché à nouveau avant la dernière 2kitération, moment où il sera transposé à la 4kvingtième position à l'infini. Un nombre premier n'est pas transposé jusqu'à ce que son tour arrive, pour ainsi dire, alors tous les nombres premiers sont mélangés. Mais nous pouvons facilement dresser une liste des victimes innocentes en imprimant simplement le premier élément à transposer à la deuxième itération et à chaque itération étrange. La liste est la suivante: 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
3
@ Sherlock9 Fait! Si approuvé, ce sera https://oeis.org/A266679 . Bonne année!
Théophile

Réponses:

5

Pyth, 19 22

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

Une implémentation assez naïve de la réponse golfscript de @ PeterTaylor .

Essayez-le en ligne ici

Ceci utilise les mêmes astuces pour convertir une boucle while en un pli que l’autre programme Pyth ci-dessous.


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

Une copie naïve de l' algorithme de @ Sp3000 traduit en Pyth.

Vous pouvez l'essayer en ligne ici

Les utilisations réduisent (nom du python pour fold) pour émuler la boucle while. Il énumère ce range(input, 2)qui fonctionne en Pyth range(2, input)[::-1]. Les autres liés Pyth-Golfs consiste à utiliser au notlieu de <2et à l' aide yest de doubler le mode caché la valeur des arguments numériques.

FryAmTheEggman
la source
21

> <>, 52 45 octets

Page Esolangs pour> <>

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

Il y a beaucoup d'éléments de copie et de déplacement, grâce aux nombreux modulo et multiplications nécessaires. La logique est exactement la même que ma solution Python .

Prend la saisie via un point de code à partir de STDIN, par exemple "!" = 33 -> 75.

Sp3000
la source
10
Et vous avez reçu le prix du format de saisie le plus délicat de tous les temps: P
Caridorc
+1 de toute façon, ne vous inquiétez pas :)
Caridorc
@ Sp3000 IMO, cela ne devrait compter que pour un
SuperJedi224
@ SuperJedi224 En fait, selon ce méta post, il semble -vqu'il
s'agisse de
17

Python 2, 58 octets

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

Comme la plupart des autres réponses, l’idée est de travailler en arrière.


Appelons step k+1step ipour que itous les multiples de isoient échangés. Nous avons besoin de deux observations simples:

  • La position ndans le tableau n’est inversée à l’étape que isi nest divisible par i,
  • Regardez si vous êtes le nombre le plus bas ou le nombre le plus élevé du swap n/i mod 2. Si ce chiffre est 1, vous êtes le nombre le plus bas (et sera échangé), sinon vous êtes le nombre le plus élevé (et échangé).

Cela nous donne un algorithme pour travailler en arrière. Essayons avec 6, en partant de la dernière étape i = 6:

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

Alors maintenant, nous savons que le nombre vient de la position 12. Ensuite:

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)

Alors maintenant, nous savons que cela venait de 16 ans auparavant. Finalement:

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)

Comme il s’agit de la première étape (rappelez-vous k+1), nous avons terminé et le numéro qui se termine en position 6 provenait de la position 14, c’est-à-dire que le 6e numéro du fusil de chasse est 14.

Alors maintenant, l'explication 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
Sp3000
la source
façon intéressante d'écrire i-1comme~-i
mbomb007
6
@ mbomb007: d'accord. Clever cependant, car il a le même sens mais élimine le besoin d'un espace après while. Beau travail, Sp3000.
Alex A.
Le plus court je pouvais obtenir cela en pyth était en utilisant réduire:u+G**H!%GHty%/GH2rhQ2Q
FryAmTheEggman
1
@FryAmTheEggman, Sp3000, ne va-t-il pas poster ça?
Martin Ender
@ MartinBüttner Je ne l'avais pas posté à l'origine car je pensais que c'était trop d'une copie. Je vais le poster comme une réponse CW pour le moment.
FryAmTheEggman
6

Haskell, 68 octets

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

Probablement plus golfable, en particulier la première rangée. Ceci définit une fonction squi prend net retourne le nnuméro du fusil de chasse.

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]

Explication

La fonction d'assistance #prend deux nombres net krenvoie le knombre e dans la liste définie en appliquant l'opération d'échange de paires à chaque nnombre. Par exemple, l'appliquer aux 20 premiers nombres avec les n = 4rendements suivants:

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

Le résultat de s nest obtenu en réduisant ("pliage") la liste [2..n]par la fonction de second ordre (.).(#), qui prend un nombre met une fonction f(initialement la fonction d'identité id), et renvoie une fonction qui prend ket retourne f (m # k). Par exemple, dans le cas où n = 4la liste [2,3,4]est réduite à une fonction qui prend ket retourne id (4 # (3 # (2 # k))). Le idn'est nécessaire que pour le cas de base n = 1, où la liste est vide. Enfin, nous donnons cette fonction à l’entrée k = n, en obtenant le nnuméro du fusil de chasse.

Zgarb
la source
6

CJam, 32 octets

Juste en suivant les spécifications au point. Exécuter les instructions sur un ensemble plus volumineux afin de ne pas affecter le nième nombre.

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

Essayez-le en ligne ici

Optimiseur
la source
5

Ruby, 92 octets

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

Mon premier effort de golf de code. Pas basé sur une autre réponse.


Maintenant que j’ai jeté un coup d’œil aux autres, j’ai remarqué que la plupart ne définissaient qu’une fonction, et non un programme complet qui accepte les entrées et produisait des sorties. L'OP a demandé un programme complet avec entrée et sortie. Est-il d'usage d'ignorer de telles exigences?


84 octets

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

Après avoir examiné d'autres réponses et réalisé qu'une solution itérative est possible.

Salomon Slow
la source
2
Quelques améliorations pour votre solution à 84 octets: 1. Passez ARGVà la solution $*magique globale. 2. Le to_sest inutile. 3. Au lieu d’affecter à dà nsur une ligne séparée, il suffit d=n=...de supprimer un personnage. Beau travail pour votre premier golf! :)
Poignée de porte
1
Où est-ce que je demande un programme complet? "Vous pouvez écrire un programme ou une fonction ...";) (Ceci est également la valeur par défaut pour les défis de code-golf , mais je l'inclue généralement par souci d'exhaustivité.)
Martin Ender
Pour ajouter aux suggestions de @ Doorknob, deux ensembles de crochets sur la n+=ligne sont inutiles et vous ==0pouvez modifier les deux occurrences de en toute sécurité <1.
Peter Taylor
5

Python 2, 97 79 caractères

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)

Il détermine pour chaque index la valeur correcte en recherchant récursivement le nombre à l'envers. L'algorithme a été découvert indépendamment.

edit: Maintenant, il n’imprime que le nnuméro th à la place des premiers nnuméros. Bien sûr, une approche itérative serait plus courte, mais je ne veux pas copier le code de Sp3000.

Jakube
la source
Oui, je pense que tout le monde va converger vers cela. J'ai trouvé la g(i,i)partie particulièrement agaçante cependant ...
Sp3000
2
La langue doit être marquée comme Python 2, à cause de la printdéclaration.
mbomb007
@ mbomb007 Corrigé.
Jakube
4

Haskell, 79 octets

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

Utilisation: p 66quelles sorties145

Pas grand chose à expliquer: la fonction #calcule de manière récursive le numéro du fusil de chasse à la position idu pas s. p nrenvoie le nombre à la position ndu pas n.

nimi
la source
Oh, je n'ai pas vu votre réponse avant de soumettre la mienne. On dirait que nous avons des approches assez différentes.
Zgarb
4

k, 41 octets

{{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 et y sont les premier et deuxième arguments implicites
  • $[b;t;f] opérateur ternaire, évalue b suivi de t / f respectivement
  • b!a un modulo b
  • _ étage, jette le résultat de la division sur un
  • % division
  • {...}/[x;y] prime {...} avec x et applique sur la liste y, est équivalent à f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
  • | sens inverse
  • ! Fonction iota, générer la liste 0 à n-1
Mollmerx
la source
4

Common Lisp, 113 91

(itératif: 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, récursif: 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)))))

Exemple

Avec la version récursive:

(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

Des tests

Contrôles et mesures pour la version itérative:

(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
coredump
la source
4

Mathematica, 53 49 octets

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

J'ai décidé de jouer au golf avec mon implémentation de référence. Le est le symbole Unicode pour "divise" et compte pour 3 octets. Sinon, cela utilise le même algorithme que tout le monde.

Il définit une fonction non nommée qui prend ncomme paramètre unique et renvoie le nnuméro du fusil de chasse.

Martin Ender
la source
4

GolfScript, 27 caractères

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

Explication

Si f(i, n)est la valeur à la position naprès les i-1transformations, on a

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

^dénote bitwise xor; donné l'entrée n, nous voulons calculer f(n, n).

La conversion d'une fonction récursive en une boucle est sans intérêt; ce qui est intéressant est la façon dont

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

peut être réécrit. L’approche la plus évidente consiste à dire qu’il doit être

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

pour certains g. Évidemment galterne entre 1et -1, puisque les positions changent alternativement de haut en bas; depuis g(1) = 1(car 1swaps jusqu'à 2), nous avons

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

**dénote une exponentiation. Les économies finales proviennent de la réécriture de cette

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
}/
Peter Taylor
la source
Étant donné que vous avez les réponses les plus courtes GS et CJam, pourquoi ne pas également avoir la réponse Pyth la plus courte? u-G*H^_!%GH/GHrhQ2QSi vous ne voulez pas poster cela vous-même, dites-le moi / ajoutez-le à la réponse CW.
FryAmTheEggman
@FryAmTheEggman, je ne suis peut-être pas très pratiqué à CJam, mais je peux au moins le lire plus ou moins. Je n'ai aucune idée de ce que dit le code Pyth dans votre commentaire, bien que, d'après le contexte, je suppose que c'est un portage de cette réponse. Il est donc préférable de le poster, car vous pouvez répondre à des questions à ce sujet.
Peter Taylor
4

Julia, 61 57 octets

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

Cela crée une fonction non nommée qui prend un seul argument net renvoie le nnuméro du fusil de chasse. Pour l'appeler, donnez-lui un nom, par exemple f=n->(...).

Exemples:

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

Actuellement, ceci est basé sur la réponse en Python de @ Sp3000 . Je reviendrai bientôt sur ce point car il doit exister un moyen plus rapide de procéder de la sorte à Julia par rapport à ce que j'ai fait ici. Toute entrée est la bienvenue, comme toujours.

Alex A.
la source
3

CJam, 28 27 octets

C’est donc un peu gênant ... avant de poster ceci, j’ai essayé de jouer au golf moi-même et j’ai atteint 30 octets dans CJam. Aucune des réponses existantes n'a encore battu. Entre temps, j'ai également réussi à supprimer trois octets supplémentaires. Il y a une solution Pyth plus courte dans un commentaire, mais rien n’a été posté dans une réponse, alors la voici. Peut-être que cela inspire les personnes APL / J à essayer un peu plus fort (ou que quelqu'un publie réellement la solution Pyth) avant que je n'accepte ma propre réponse. ;)

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

Testez-le ici.

Explication

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.";
Martin Ender
la source
3

J, 34 32 octets

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

Je vais essayer de jouer au golf un peu plus et ajouter quelques explications plus tard.

Essayez-le en ligne ici.

randomra
la source
2

TI-Basic 83/84, 40 octets

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

Informations sur TI-Basic

Timtech
la source
1

Ruby, 57 47 octets

Ceci est essentiellement SP3000 solution Python de (avec la suggestion de xnor ) traduit à Ruby. Je pourrais probablement jouer au golf dans quelques endroits cependant.

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