Pourtant, des paires inutilisées

21

Définissons une séquence d'entiers positifs. Nous définirons la séquence des nombres pairs comme étant le double du terme précédent. Les indices impairs de la séquence seront le plus petit entier positif n'apparaissant pas encore dans la séquence.

Voici les premiers termes du couple.

1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

Vous pouvez également y voir la liste des paires concaténées (n, 2n) où n est l'entier positif le moins utilisé jusqu'à présent.

Tâche

Étant donné un nombre n en entrée, calculer le n ème terme dans cette séquence.

Il s'agit de code-golf , vous devez donc viser à minimiser la taille de votre code source, mesurée en octets.

OEIS A036552

code-golf sequence Assistant de blé
la source
Le fait que les indices impairs de la séquence seront le plus petit entier positif n'apparaissant pas encore dans la séquence. est hors de propos, non?
Adám
1
Et quelles paires ?
Adám
@ Adám Non ce n'est pas le cas. Je ne sais pas ce qui vous donne cette impression peut-être que j'ai mal formulé cela.
Wheat Wizard
1
@ Adám une autre façon de penser la séquence est qu'elle se compose de paires concaténées (n,2n)et que chaque nombre n'apparaît qu'une seule fois. Chaque paire est choisie pour être la plus petite possible tout en respectant cette dernière contrainte.
Martin Ender
3
L'évaluation 2-adique des éléments impairs de la série est toujours égale. Pourrait être utile à quelqu'un.
CalculatorFeline

Réponses:

11

Haskell, 40 octets

l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

Base zéro. lconstruit progressivement la séquence à partir d'une liste paresseuse d'entiers restants.

Christian Sievers
la source
7

JavaScript (ES6), 92 82 69 67 65 octets

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

Comment?

Nous suivons:

  • La dernière valeur insérée b .
  • Toutes les valeurs précédemment rencontrées dans la table de recherche a .

En interne, nous utilisons un index basé sur 0 i . Les comportements impairs et pairs sont donc inversés:

  • Aux positions impaires, la valeur suivante est simplement 2 * b.

  • Aux positions paires, nous utilisons la fonction récursive g () et la table de recherche a pour identifier la plus petite valeur correspondante:

    (g = k => a[k] ? g(k + 1) : k)(1)

Pour économiser quelques octets, i est initialisé à {}plutôt qu'à 0. Cela nous oblige à utiliser:

  • i^npour comparer i avec n parce ({}) ^ n === nque alors ({}) - névalue à NaN.
  • -~iincrémenter i , car ({}) + 1générerait une chaîne.

Démo

Afficher l'extrait de code

Arnauld
la source
60 octets
Shaggy
5

Python 3 , 80 72 69 octets

-7 octets grâce à M. Xcoder !

f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

Essayez-le en ligne!

notjagan
la source
1
Vous pouvez remplacer set(...)par `{* ...} pour 78 octets
M. Xcoder
@ Zacharý Vous rappeliez-vous mon commentaire? Si c'est le cas, un ensemble en Python 3 peut être à la {*...}place de set(...).
M. Xcoder
Je commentais sans réfléchir, j'ai réalisé quelques instants plus tard que {...for...in...}ce serait plus d'adieux.
Zacharý
En fait, cela économiserait 4 octets, car vous l'utilisez deux fois
M. Xcoder
69 octets. (et il n'utilise pas Truepour 1)
Wheat Wizard
3

Mathématiques , 56 53 octets

-3 octets merci JungHwan Min !

(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&

Essayez-le en ligne!

Basé sur l'expression Mathematica donnée dans le lien OEIS.

notjagan
la source
1
Aussi 53 octets:Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]&
JungHwan Min
3

PHP , 64 octets

for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;

Essayez-le en ligne!

PHP , 77 octets

for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;

Essayez-le en ligne!

PHP , 78 octets

for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;

Essayez-le en ligne!

Jörg Hülsermann
la source
3

PHP, 56 octets

while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

PHP, 75 72 octets

for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

Essayez-le en ligne

Titus
la source
3

05AB1E , 16 15 14 octets

1 indexé.
Utilise le fait que la représentation binaire d'éléments à des indices impairs dans la séquence se termine par un nombre pair de zéros: A003159 .

Lʒb1¡`gÈ}€x¹<è

Essayez-le en ligne!

Explication

L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)
Emigna
la source
3

Python 2 , 59 51 49 octets

f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

Essayez-le en ligne!

Contexte

Chaque n entier positif peut être exprimé uniquement comme n = 2 o (n) c (n) , où c (n) est impair.

Laissez ⟨a n ⟩ n> 0 être la séquence de la spécification de défi.

Nous affirmons que, pour tous les entiers positifs , n , o (a 2n-1 ) est pair. Puisque o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , cela revient à affirmer que o (a 2n ) est toujours impair.

Supposons que la réclamation soit fausse et que 2m-1 soit le premier indice impair de la séquence tel que o (a 2m-1 ) soit impair. Notez que cela fait de 2m le premier indice pair de la séquence tel que o (a 2m-1 ) est pair.

o (un 2m-1 ) est impair et 0 est pair, donc un 2m-1 est divisible par 2 . Par définition, un 2 m-1 est le plus petit entier positif ne figurant pas encore dans la séquence , ce qui signifie que d' un 2 m-1 /2 doit avoir comparu devant. Soit k soit le (premier) indice d' un 2m-1 / deux en un .

Puisque o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 est pair, la minimalité de n implique que k est impair. À son tour, cela signifie que un k + 1 = 2a k = a 2m-1 , en contradiction avec la définition d' un 2m-1 .

Comment ça marche

encore à venir

Dennis
la source
3

R , 70 69 65 octets

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

Essayez-le en ligne!

Une fonction anonyme qui prend un argument. Fpar défaut à FALSEou de 0sorte que l'algorithme évalue correctement qu'aucun entier positif ne se trouve encore dans la séquence.

L'algorithme génère les paires dans une forboucle de la manière suivante (où iva de 2à 2nby 2):

           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i
Giuseppe
la source
2

Haskell , 63 octets

g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2

Essayez-le en ligne!

Celui-ci abuse au maximum de l'évaluation paresseuse de Haskell.

Assistant de blé
la source
2

Perl 6 , 50 octets

{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

Essayez-le en ligne!

  • 1, { ... } ... *est une séquence infinie générée paresseusement où chaque terme après le premier est fourni par le bloc de code délimité par des accolades. Étant donné que le bloc fait référence à la@_ tableau, il reçoit la séquence actuelle entière dans ce tableau.
  • Si le nombre actuel d'éléments est impair ( @_ % 2), nous générons un élément même indexé, de sorte que l'élément suivant est le double du dernier élément que nous avons jusqu'à présent: 2 * @_[*-1].
  • Dans le cas contraire, on obtient le premier entier positif qui ne semble pas encore dans la séquence: first * ∉ @_, 1..*.
  • $_est l'argument de la fonction externe. Il indexe dans la séquence infinie, donnant la valeur de retour de la fonction.
Sean
la source
1

Mathematica, 82 octets

(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

Essayez-le en ligne!

J42161217
la source
58 octets dans Mathematica (bien que je devrais probablement poster une réponse séparée car l'idée est assez différente).
notjagan
L'avez-vous copié à partir du lien OEIS?
J42161217
Je l'ai modifié pour l'adapter à la tâche et pour être plus golfé, mais c'est plus ou moins la même chose que le lien OEIS.
notjagan
1
@not post a new answer if you want and credit the author
J42161217
1

k , 27 octets

*|{x,*(&^x?!y;|2*x)2!y}/!2+

1 indexé. Essayez-le en ligne!

Utiliser (!y)^xau lieu de&^x?!y travaux aussi.

zgrep
la source
1

C # (compilateur interactif Visual C #) , 82 octets

x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

Essayez-le en ligne!

-6 octets grâce à @ASCIIOnly!

dana
la source
C # 8 est peut-être trop nouveau pour être commun sur les interprètes en ligne pour l'instant, ajouté au fait que csi est une chose Mono, vous devrez donc attendre que Mono l'implémente et l'ajoute à une version stable (s'il ne l'a pas) t déjà)
ASCII uniquement
malheureusement, il n'est pas facile de vérifier cela en C #
ASCII uniquement le
Utilisez-le pour commencer? Mais oui, cela ne semble pas être une chose simple. docs.microsoft.com/en-us/dotnet/api/…
dana
1
86? - ne pensez pas que les :s sont nécessaires car ce sera le plus grand nombre de la liste
ASCII uniquement
Aussi 2.0=>2f
dana
0

Clojure, 102 octets

#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

Itère les ntemps pour construire la séquence et retourne le ne élément, indexé 1.

NikoNyrh
la source
0

Rubis, 60 octets

->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

0 indexé. Nous bouclons les n/2+1temps, générant deux valeurs à chaque fois et les stockant en remplissant un tableau à leurs indices. v+v*n%2donne la sortie, que ce soit vou en v*2fonction de la parité n.

histocrate
la source
0

Rubis , 49 octets

->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

Commencez par [0], ajoutez des paires au tableau jusqu'à ce que nous ayons au moins n + 1 éléments, puis prenez le n + 1th (basé sur 1)

Essayez-le en ligne!

GB
la source
0

JavaScript (ES6), 60 65 octets

Une solution itérative.

n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

Moins golfé

n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;  
}

Tester

F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
Développer l'extrait

edc65
la source
0

Gelée , 13 12 10 octets

ḤRọ2ḂĠZFị@

Cela utilise l'observation de ma réponse Python .

Essayez-le en ligne!

Comment ça marche

ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.
Dennis
la source