Noch nicht verwendete Paare

21

Definieren wir eine Folge positiver Ganzzahlen. Wir werden die Reihenfolge auf geraden Zahlen so definieren, dass sie das Doppelte des vorherigen Terms beträgt. Die ungeraden Indizes der Sequenz sind kleinste positive ganze Zahlen, die noch nicht in der Sequenz vorkommen.

Hier sind die ersten paar Begriffe.

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

Sie können sich dies auch als die Liste der verketteten Paare (n, 2n) vorstellen, wobei n die bisher am wenigsten verwendete positive Ganzzahl ist.

Aufgabe

Berechnen Sie bei einer Zahl n als Eingabe den n- ten Term in dieser Reihenfolge.

Dies ist Codegolf, daher sollten Sie versuchen, die Größe Ihres Quellcodes in Byte zu minimieren.

OEIS A036552

code-golf sequence Weizen-Assistent
quelle
Die Tatsache, dass die ungeraden Indizes der Sequenz die kleinste positive ganze Zahl sind, die noch nicht in der Sequenz vorkommt. ist irrelevant, oder?
Adám
1
Auch welche Paare ?
Adám
@ Adám Nein das ist nicht der Fall. Ich bin mir nicht sicher, was Ihnen diesen Eindruck vermittelt, vielleicht habe ich das schlecht formuliert.
Weizen-Assistent
1
@ Adám Eine andere Möglichkeit, sich die Sequenz vorzustellen, besteht darin, dass sie aus verketteten Paaren besteht (n,2n)und jede Zahl nur einmal vorkommt. Jedes Paar wird so gewählt, dass es das kleinstmögliche ist, während die letztgenannte Einschränkung eingehalten wird.
Martin Ender
3
Die 2-adische Bewertung von ungeraden Elementen der Reihe ist immer gerade. Könnte jemandem nützlich sein.
CalculatorFeline

Antworten:

11

Haskell, 40 Bytes

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

Nullbasiert. lErstellt die Sequenz inkrementell aus einer verzögerten Liste verbleibender Ganzzahlen.

Christian Sievers
quelle
7

JavaScript (ES6), 92 82 69 67 65 Bytes

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

Wie?

Wir verfolgen:

  • Der zuletzt eingefügte Wert b .
  • Alle zuvor ermittelten Werte in der Nachschlagetabelle a .

Intern verwenden wir einen 0-basierten Index i . Gerade und ungerade Verhaltensweisen werden daher invertiert:

  • Bei ungeraden Positionen ist der nächste Wert einfach 2 * b.

  • An geraden Positionen verwenden wir die rekursive Funktion g () und die Nachschlagetabelle a , um den kleinsten Übereinstimmungswert zu identifizieren:

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

Um ein paar Bytes zu sparen, wird i auf {}anstatt initialisiert 0. Dies zwingt uns zu verwenden:

  • i^ni mit n zu vergleichen, weil ({}) ^ n === nwährend ({}) - nauswertet NaN.
  • -~ium i zu erhöhen , weil ({}) + 1eine Zeichenfolge generiert würde.

Demo

Code-Snippet anzeigen

Arnauld
quelle
60 Bytes
Shaggy
5

Python 3 , 80 72 69 Bytes

-7 Bytes dank Mr. Xcoder !

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

Probieren Sie es online!

notjagan
quelle
1
Sie können set(...)mit `{* ...} für 78 Bytes
Mr. Xcoder
@ Zacharý Haben Sie auf meinen Kommentar verwiesen? Wenn ja, ein Satz in Python 3 kann {*...}statt set(...).
Mr. Xcoder
Ich kommentierte ohne nachzudenken, ich erkannte ein paar Momente später, dass {...for...in...}es mehr Byes geben würde.
Zacharý
Eigentlich würde es 4 Bytes sparen, weil Sie es zweimal verwenden
Mr. Xcoder
69 Bytes. (und es wird nicht Truefür 1 verwendet)
Weizen-Assistent
3

Mathematik , 56 53 Bytes

-3 Bytes danke JungHwan Min !

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

Probieren Sie es online!

Basierend auf dem Mathematica-Ausdruck im OEIS-Link.

notjagan
quelle
1
Auch 53 Bytes:Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]&
JungHwan Min
3

PHP, 56 Bytes

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

PHP, 75 72 Bytes

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

Probieren Sie es online aus

Titus
quelle
3

05AB1E , 16 15 14 Bytes

1-indiziert.
Verwendet die Tatsache, dass die binäre Darstellung von Elementen an ungeraden Indizes in der Sequenz mit einer geraden Anzahl von Nullen endet: A003159 .

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

Probieren Sie es online!

Erläuterung

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
quelle
3

Python 2 , 59 51 49 Bytes

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

Probieren Sie es online!

Hintergrund

Jede positive ganze Zahl n kann eindeutig ausgedrückt werden als n = 2 o (n) c (n) , wobei c (n) ungerade ist.

Lassen Sie ⟨a n ⟩ n> 0 die Sequenz aus der Herausforderung spec sein.

Wir behaupten, dass für alle positiven ganzen Zahlen n , o (a 2n-1 ) gerade ist. Da o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 ist, entspricht dies der Behauptung, dass o (a 2n ) immer ungerade ist.

Angenommen, die Behauptung ist falsch und 2m-1 sei der erste ungerade Index der Folge, so dass o (a 2m-1 ) ungerade ist. Beachten Sie, dass 2m der erste gerade Index der Sequenz ist, sodass o (a 2m-1 ) gerade ist.

o (a 2m-1 ) ist ungerade und 0 ist gerade, also ist a 2m-1 durch 2 teilbar . Per Definition ist eine 2m-1 die kleinste positive Ganzzahl, die noch nicht in der Sequenz vorkommt , was bedeutet, dass zuvor eine 2m-1 /2 vorgekommen sein muss. Sei k der (erste) Index von a 2m-1 /2 in a .

Da o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 gerade ist, impliziert die Minimalität von n , dass k ungerade ist. Dies bedeutet wiederum, dass a k + 1 = 2a k = a 2m-1 ist , was der Definition von a 2m-1 widerspricht .

Wie es funktioniert

noch kommen

Dennis
quelle
3

R , 70 69 65 Bytes

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

Probieren Sie es online!

Eine anonyme Funktion mit einem Argument. FDer Standardwert ist FALSEoder, 0damit der Algorithmus korrekt einschätzt, dass sich noch keine positiven ganzen Zahlen in der Sequenz befinden.

Der Algorithmus erzeugt die Paare in einer forSchleife in der folgenden Weise (wo iaus geht 2zu 2ndurch 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
quelle
2

Haskell , 63 Bytes

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

Probieren Sie es online!

Dieser missbraucht Haskells faule Einschätzung in vollem Umfang.

Weizen-Assistent
quelle
2

Perl 6 , 50 Bytes

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

Probieren Sie es online!

  • 1, { ... } ... *ist eine träge erzeugte unendliche Folge, bei der jeder Ausdruck nach dem ersten durch den durch geschweifte Klammern getrennten Codeblock bereitgestellt wird. Da der Block auf die@_ Array , empfängt er die gesamte aktuelle Sequenz in diesem Array.
  • Wenn die aktuelle Anzahl von Elementen ungerade (ist @_ % 2), sind wir ein noch indiziertes Element zu erzeugen, so dass das nächste Element Doppel das letzte Element ist , haben wir so weit: 2 * @_[*-1].
  • Ansonsten bekommen wir die erste positive ganze Zahl, die noch nicht in der Reihenfolge angezeigt wird: first * ∉ @_, 1..*.
  • $_ist das Argument für die äußere Funktion. Es indiziert in die unendliche Folge und gibt den Rückgabewert der Funktion an.
Sean
quelle
1

Mathematica, 82 Bytes

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

Probieren Sie es online!

J42161217
quelle
58 Bytes in Mathematica (obwohl ich wahrscheinlich nur eine separate Antwort posten sollte, da die Idee ganz anders ist).
Notjagan
Haben Sie das vom OEIS-Link kopiert?
J42161217
Ich habe es modifiziert, um es der Aufgabe anzupassen und mehr Golf zu spielen, aber es ist mehr oder weniger dasselbe wie der OEIS-Link.
Notjagan
1
@ Poste keine neue Antwort, wenn du willst und
schreibe
1

k , 27 Bytes

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

1-indiziert. Probieren Sie es online!

Verwenden (!y)^xstatt &^x?!yauch arbeiten.

zgrep
quelle
1

C # (Visual C # Interactive Compiler) , 82 Byte

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

Probieren Sie es online!

-6 Bytes dank @ASCIIOnly!

Dana
quelle
C # 8 ist möglicherweise zu neu für Online-Dolmetscher. Hinzu kommt, dass es sich bei csi um eine Mono-Sache handelt. Sie müssen also warten, bis Mono sie implementiert und zu einem stabilen Build hinzugefügt hat (falls dies nicht der Fall ist). t schon)
Nur ASCII
Leider ist es nicht einfach, dies in C # zu überprüfen
ASCII
Verwenden Sie dies, um zu starten? Aber ja, es scheint keine einfache Sache zu sein. docs.microsoft.com/en-us/dotnet/api/…
dana
1
86? - Denken Sie nicht, dass die :s benötigt werden, da dies die größte Zahl in der Liste ist
Nur ASCII
Also 2.0=>2f
Dana
0

Clojure, 102 Bytes

#(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))))%)

Durchläuft ndie Sequenz, um sie aufzubauen, und gibt das erste nElement mit einem Index zurück.

NikoNyrh
quelle
0

Ruby, 60 Bytes

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

0-indiziert. Wir schleifen n/2+1Zeiten, generieren jedes Mal zwei Werte und speichern sie, indem wir ein Array an ihren Indizes auffüllen. v+v*n%2gibt die Ausgabe entweder voderv*2 abhängig von der Parität von n.

Histokrat
quelle
0

Rubin , 49 Bytes

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

Beginnen Sie mit [0], fügen Sie dem Array Paare hinzu, bis wir mindestens n + 1 Elemente haben, und nehmen Sie dann das n + 1te (1-basiert).

Probieren Sie es online!

GB
quelle
0

JavaScript (ES6), 60 bis 65 Byte

Eine iterative Lösung.

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

Weniger golfen

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;  
}

Prüfung

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))
Erweitern Sie das Snippet

edc65
quelle
0

Jelly , 13 12 10 Bytes

ḤRọ2ḂĠZFị@

Dies nutzt die Beobachtung von meiner Python-Antwort .

Probieren Sie es online!

Wie es funktioniert

Ḥ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
quelle