La séquence de sauts

19

Considérez la séquence suivante:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Semble assez sans motif, non? Voici comment ça fonctionne. En commençant par 0, sauter des nentiers, en ncommençant par 1. C'est le numéro suivant de la séquence. Ensuite, ajoutez tous les nombres "sautés" et qui n'ont pas encore été vus dans l'ordre croissant. Ensuite, incrémentez net sautez du dernier nombre ajouté. Répétez ce modèle.

Ainsi, par exemple, lorsque nous atteignons 11, nous y sommes n=5. Nous incrémentons npour être n=6, sautons à 17, puis ajoutons 13 14 15 16puisque ceux-ci n'ont pas encore été vus. Notre prochain saut est n=7, donc l'élément suivant de la séquence est 23.

Le défi

Étant donné l'entrée x, sortez le xterme de cette séquence, les premiers xtermes de la séquence, ou créez une liste infinie des termes de la séquence. Vous pouvez choisir l'indexation 0 ou 1.

E / S et règles

  • L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique .
  • L'entrée et la sortie peuvent être supposées correspondre au type de numéro natif de votre langue.
  • Un programme complet ou une fonction sont acceptables. S'il s'agit d'une fonction, vous pouvez renvoyer la sortie plutôt que de l'imprimer.
  • Les failles standard sont interdites.
  • Il s'agit de donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) l'emporte.
AdmBorkBork
la source
Ce n'est apparemment pas (encore?) Sur OEIS
JayCe
@JayCe Je ne suis pas surpris - c'est une séquence assez arbitraire.
AdmBorkBork

Réponses:

24

JavaScript (ES7), 41 octets

Renvoie le nième terme de la séquence, indexé 0.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Essayez-le en ligne!

Comment?

Cas principal: n>3

Les quatre premiers termes de la séquence sont spéciaux, alors mettons-les de côté pour l'instant.

Pour , la séquence ressemble à ceci:n>3

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

On peut remarquer qu'il existe en fait deux sous-séquences entrelacées:

  • La plupart des valeurs appartiennent à la sous-séquence pour laquelle nous avons simplement:A

    A(n)=n1
  • Certaines autres valeurs appartiennent à la sous-séquence (mise en évidence entre parenthèses dans le schéma ci-dessus) dont les indices suivent la séquence arithmétique 3, 3, 4, 6, 9, 13, 18, 24 ... et pour laquelle nous avons:B

    B(n,k)=n+k1

    est l'indice dans la séquence principale et k est l'indice de la sous-séquence B .nkB

Les indices de dans la séquence principale sont donnés par:B

nk=k2k+62

Étant donné , nous savons que le terme correspondant dans la séquence principale appartient à B si n est une solution entière de l'équation quadratique:nBn

x2x+62n=0

dont le discriminant est:

Δ=14(62n)=8n23

et dont la solution positive est:

x=1+Δ2

Nous attendons pour être un entier. D'où le test:Δ

(d = (n-- * 8 - 23) ** .5) % 1

Cas particuliers: 0n3

Pour , le discriminant est négatif et prend sa racine carrée dans NaN . Pour n = 3n<3n=3 , le discriminant est . Par conséquent, ces quatre premiers termes de la séquence sont considérés comme appartenant à la sous-séquence B .1B

Si nous appliquions simplement notre formule standard n - ~ d / 2 , nous obtiendrions:

12,12,32,3

au lieu de:

0,1,3,2

C'est pourquoi nous avons XOR ces résultats avec .0,1,2 and 1

Arnauld
la source
10

Husk , 12 octets

Θṁṙ_1C+ḣ2tNN

Essayez-le en ligne!

Sorties sous forme de liste infinie. Voici une version qui imprime le premier N .

Explication

Θṁṙ_1C + ḣ2tNN - Programme complet. Ne prend aucune entrée, sort vers STDOUT.
         tN - Construit la liste infinie de nombres naturels, à partir de 2.
      + ḣ2 - Et ajoutez-y [1, 2]. Rendements [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Coupez la liste infinie d'entiers positifs en morceaux de ceux
               tailles. Rendements [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 ṁ - Cartographiez et aplatissez les résultats par la suite.
  ṙ_1 - Faites pivoter chacun vers la droite d'une unité.
               Rendements [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - Prepend a 0. Rendements [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]
M. Xcoder
la source
7

Haskell , 43 octets

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

Essayez-le en ligne!

Définit une liste infinie:

  0:1:3:2:(5!3)
 0:1:3:2:5:4:(8!4)
 0:1:3:2:5:4:8:6:7:(12!5)
 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) 
Lynn
la source
4

Gelée , 15 octets

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

Il s'agit d'un programme complet qui, étant donné n , imprime les n premiers éléments de la séquence.

Essayez-le en ligne!

Comment ça fonctionne

0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.


+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.
Dennis
la source
3

C (gcc), 73 67 64 octets

t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

Essayez-le en ligne!

Définit une fonction fqui prend l'index 0 net produit le nnuméro e dans la séquence.

Nous pouvons analyser la séquence comme suit:

f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

Nous traitons d'abord la section centrale:

for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

Notez que les arguments de gauche (4, 6, 9, 13, ...) suivent un modèle: ajoutez d'abord deux, puis ajoutez trois, puis ajoutez quatre, et ainsi de suite. Nous commençons à t=4et ajoutons d(qui commence à 2) chaque itération de la boucle, incrémentant ddans le processus.

Le corps de la boucle est plus intéressant. N'oubliez pas que nous voulons cartographier 4 à 5, 6 à 8, 9 à 12, etc .; c'est juste ajouter d-1si xc'est t. Cependant, cette logique précède le dernier cas, f(n) = n - 1donc nous savons que nous allons soustraire 1 à la fin. Par conséquent, nous pouvons simplement ajouter dif x == t( x-t||(x+=d)). Cependant, nous aurons aussi besoin de sortir de la boucle immédiatement après cela - si l' on ajoute que pour dobtenir l'aspect absurde d+=x+=d, ce qui fera toujours l' d<xéchec condition.

Cela couvre tout sauf les quatre premières valeurs. En les regardant en binaire, on obtient:

00 -> 00
01 -> 01
10 -> 11
11 -> 10

Donc, nous voulons retourner le dernier bit si 2 <= x < 4. Ceci est accompli avec x^x/2. x/2donne le deuxième bit le moins significatif, donc XORing cela avec le numéro d'origine retourne le dernier bit si le nombre est 2 ou 3.

Poignée de porte
la source
3

Gelée ,  13  10 octets

-3 Merci à Dennis (utilisez l'indexation 0 pour sauver 2 de la configuration de la somme cumulée et d'un décrément final)

Ḷ»2Äi+_>2$

Un lien monadique acceptant un entier, 0- indexé n , qui renvoie un entier, a (n)

Essayez-le en ligne! Ou voir une suite de tests

Jonathan Allan
la source
Agréable! J'avais ḶÄ+3i+’, mais aucune idée de comment gérer les cas de bord.
Dennis
J'ai aussi Ḷ»ạ¥3pour Ḋ3,2;- le sentiment qu'il devrait y avoir un terser pour ce morceau.
Jonathan Allan
Ḷ»2Äi+_>2$enregistre 3 octets, avec une indexation basée sur 0.
Dennis
Oh golf génial! J'étais coincé dans un pays à indice 1.
Jonathan Allan
2

MATL , 22 octets

1y:"t0)@+h5M:yX-h]qw:)

Sort les premiers ntermes de la séquence.

Essayez-le en ligne!

Explication

1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display
Luis Mendo
la source
J'aime le smiley à la fin, maintenant je veux que tous mes programmes MATL se terminent avec le sourire. :)
sundar
@sundar Oui, je suis heureux que ce soit un idiome relativement courant en MATL :-D
Luis Mendo
1

Rubis , 73 octets

f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

Essayez-le en ligne!

Fonction récursive qui renvoie les premiers x nombres de la liste.

crashoz
la source
1

QBasic, 58 octets

DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

Sorties indéfiniment. Vous voudrez peut-être ajouter un SLEEP 1à l'intérieur de la boucle ou le faire LOOP WHILE b<100ou quelque chose comme ça afin de voir les résultats.

Cela implémente simplement la spécification. Notez que les chiffres pour lesquels nous revenons seront toujours les numéros entre le dernier numéro sauté et le numéro sauté avant celui-ci. Nous stockons donc ces limites sous aet bet utilisons une FORboucle pour imprimer tous les nombres entre elles.

DLosc
la source
1

R , 70 octets

function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

Essayez-le en ligne!

  • 1 indexé
  • -4 octets en utilisant F constante grâce à la suggestion @JAD
  • -5 octets inversant la liste grâce à la suggestion @Giuseppe
  • -2 octets supprimant les accolades inutiles dans la boucle for grâce à la suggestion @JAD
  • -2 octets utilisant setdiffau lieu dex[x %in% y]

Version précédente (79 octets)

digEmAll
la source
2
79 octets
JAD
@JAD: J'ai toujours oublié d'utiliser F / T ... Je ne peux pas m'en empêcher, je suis trop enclin à éviter les "codes dangereux": D
digEmAll
1
Construire la liste en sens inverse enregistre 5 byteset provoque un tas d'avertissements!
Giuseppe
Ce n'est même pas dangereux s'ils F/Tne sont pas redéfinis lors de la définition de la fonction. Il (IIRC) ne modifie pas la valeur globale pourF/T
JAD
1
72 octets
JAD
1

Python 2 , 123 octets

def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s    

Essayez-le en ligne!

Étant donné l'entrée x, sortir les x premiers termes de la séquence,

J'apprends Python et ces défis rendent les choses plus intéressantes.

Modifier: raser des espaces

Pignon moyen
la source
Bienvenue chez PPCG! Vous pouvez vous débarrasser de quelques autres espaces for n in range(1,z) if len(s) < z]; return s: for n in range(1,z)if len(s)<z];return s.
Laikoni
0

Gelée , 16 octets

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

Essayez-le en ligne!

Un octet de plus que la réponse Jelly existante, mais cela pourrait éventuellement être joué un peu. RÄṬŻk²Ḋ$pourrait peut-être être plus court.

18 octets

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Plus long mais différent.

dylnan
la source
0

Rubis , 63 octets

->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

Essayez-le en ligne!

0 indexé. Peut probablement être joué au golf.

Réintégrer Monica - notmaynard
la source
0

Perl 6 , 52 octets

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

Essayez-le en ligne!

Il s'agit d'une expression de générateur utilisant l' ...opérateur. Il recherche les lacunes dans la séquence précédente @_via ((^max @_)∖@_).min.?key:

      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

Le ?est nécessaire pour la valeur initiale qui n'a pas de .key. Si aucun écart n'est trouvé, il ajoute n (ici dans la $variable) à la dernière valeur de la liste, plus un pour les erreurs désactivées par 0.

Phil H
la source
0

Python 3 , 104 octets

def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

Essayez-le en ligne!

Étant donné l'entrée x, sortir les x premières "séquences"

frosqh
la source