Zdefiniujmy sekwencję dodatnich liczb całkowitych. Zdefiniujemy sekwencję na liczbach parzystych, aby była podwójna w stosunku do poprzedniego terminu. Dziwne wskaźniki sekwencji będą najmniejszą dodatnią liczbą całkowitą, która nie pojawia się jeszcze w sekwencji.

Oto kilka pierwszych warunków.

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

Można to również traktować jako listę połączonych par (n, 2n), gdzie n jest jak dotąd najmniej niewykorzystaną liczbą całkowitą dodatnią.

Zadanie

Biorąc pod uwagę liczbę n jako dane wejściowe, obliczyć n- ty składnik w tej sekwencji.

To jest golf golfowy, więc powinieneś dążyć do zminimalizowania rozmiaru kodu źródłowego mierzonego w bajtach.

OEIS A036552

Haskell, 40 bajtów

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

Zero. lprzyrostowo buduje sekwencję z leniwej listy pozostałych liczb całkowitych.

JavaScript (ES6), 92 82 69 67 65 bajtów

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

W jaki sposób?

Śledzimy:

• Ostatnia wstawiona wartość b .
• Wszystkie wcześniej napotkane wartości w tabeli odnośników a .

Wewnętrznie używamy indeksu 0 opartego I . Dziwne, a nawet zachowania są odwrócone:

• W nieparzystych pozycjach następna wartość jest po prostu 2 * b.

• W pozycjach parzystych używamy funkcji rekurencyjnej g () i tabeli odnośników a, aby zidentyfikować najmniejszą pasującą wartość:

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

Aby zaoszczędzić kilka bajtów, i jest inicjowany {}zamiast 0. Zmusza nas to do korzystania z:

• i^nporównać I z n ponieważ ({}) ^ n === nnatomiast ({}) - nma wartość NaN.
• -~izwiększyć i , ponieważ ({}) + 1wygenerowałoby ciąg.

Próbny

let f =

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

for(n = 1; n <= 20; n++) {
  console.log('a[' + n + '] = ' + f(n));
}

Python 3 , 80 72 69 bajtów

^{-7 bajtów dzięki Mr. Xcoder !}

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

Wypróbuj online!

Galaretka , 15 bajtów

Jḟ⁸ḢðḤṭṭ
0Ç¡Ḋị@

Wypróbuj online!

Matematyka , 56 53 bajtów

^{-3 bajty dzięki JungHwan Min !}

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

Wypróbuj online!

Na podstawie wyrażenia Mathematica podanego w łączu OEIS.

PHP , 64 bajty

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

Wypróbuj online!

PHP , 77 bajtów

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

Wypróbuj online!

PHP , 78 bajtów

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

Wypróbuj online!

PHP, 56 bajtów

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

PHP, 75 72 bajtów

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

Wypróbuj online

05AB1E , 16 15 14 bajtów

1-indeksowany.
Wykorzystuje fakt, że binarna reprezentacja elementów o nieparzystych indeksach w sekwencji kończy się parzystą liczbą zer: A003159 .

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

Wypróbuj online!

Wyjaśnienie

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)

Python 2 , 59 51 49 bajtów

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

Wypróbuj online!

tło

Każda dodatnia liczba całkowita n może być wyrażona jednoznacznie jako n = 2 ^{o (n)} c (n) , gdzie c (n) jest nieparzyste.

Niech ⟨a _n ⟩ _{n> 0} mieć sekwencję spec prowokacji.

Twierdzimy, że dla wszystkich liczb całkowitych dodatnich n , o (a _2n-1 ) jest parzyste. Ponieważ o (a _2n ) = o (2a _2n-1 ) = o (a _2n-1 ) + 1 , jest to równoważne z twierdzeniem, że o (a _2n ) jest zawsze nieparzyste.

Załóżmy, że twierdzenie jest fałszywe i niech 2m-1 będzie pierwszym nieparzystym indeksem sekwencji, tak że o (a _2m-1 ) jest nieparzyste. Zauważ, że dzięki temu 2m jest pierwszym parzystym indeksem sekwencji, tak że o (a _2m-1 ) jest parzyste.

O (a _2m-1 ) jest nieparzyste i 0 nawet tak _2m-1 jest podzielna przez 2 . Z definicji, _2m-1 jest najmniejsza dodatnia jeszcze nie pojawia się w sekwencji , co oznacza, że _2m-1 /2 muszą pojawiły się wcześniej. Niech k będzie (pierwszy) indeks na _2m-1 /2 w .

Ponieważ o (a _k ) = o (a _2m-1 /2) = o (a _2m-1 ) - 1 jest parzyste, minimalna liczba n oznacza, że k jest nieparzyste. To z kolei oznacza, że _{k + 1} = 2 a _k = a _{2 M 1} , w sprzeczności z definicją w _2m-1 .

Jak to działa

jeszcze przed nami

R , 70 69 65 bajtów

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

Wypróbuj online!

Anonimowa funkcja, która bierze jeden argument. przyjmuje wartość Fdomyślną FALSElub 0taką, że algorytm poprawnie ocenia, że ​​w sekwencji nie ma jeszcze dodatnich liczb całkowitych.

Algorytm generuje pary w forpętli w następujący sposób (gdzie iprzechodzi od 2do 2nprzez 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

Haskell , 63 bajty

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

Wypróbuj online!

Ten w największym stopniu narusza leniwą ocenę Haskella.

Perl 6 , 50 bajtów

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

Wypróbuj online!

• 1, { ... } ... *jest leniwie generowaną nieskończoną sekwencją, w której każdy termin po pierwszym jest dostarczany przez blok kodu rozdzielany nawiasami klamrowymi. Ponieważ blok odwołuje się do @_tablicy, otrzymuje całą bieżącą sekwencję w tej tablicy.
• Jeśli aktualna liczba elementów jest nieparzysta ( @_ % 2), mamy do generowania nawet indeksowane elementu, więc następnym elementem jest podwójna ostatni element mamy do tej pory: 2 * @_[*-1].
• W przeciwnym razie, mamy pierwszą dodatnią liczbę całkowitą, która nie ma jeszcze pojawiają się w kolejności: first * ∉ @_, 1..*.
• $_jest argumentem funkcji zewnętrznej. Indeksuje się w nieskończonej sekwencji, podając wartość zwracaną przez funkcję.

Mathematica, 82 bajty

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

Wypróbuj online!

k , 27 bajtów

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

1-indeksowany. Wypróbuj online!

Używanie (!y)^xzamiast &^x?!ydziała też.

C # (interaktywny kompilator Visual C #) , 82 bajty

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

Wypróbuj online!

-6 bajtów dzięki @ASCIIOnly!

Clojure, 102 bajty

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

Iteruje nrazy, aby zbudować sekwencję i zwraca ten nelement, 1-indeksowany.

Rubinowy, 60 bajtów

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

0-indeksowane. Pętlujemy n/2+1czasy, generując za każdym razem dwie wartości i przechowując je, wypełniając tablicę przy ich indeksach. v+v*n%2daje wyjście, albo vczy v*2w zależności od parytetu n.

Ruby , 49 bajtów

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

Zacznij od [0], dodawaj pary do tablicy, aż będziemy mieli co najmniej n + 1 elementów, a następnie weź n + 1 (na podstawie 1)

Wypróbuj online!

JavaScript (ES6), 60 65 bajtów

Iteracyjne rozwiązanie.

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

Mniej golfa

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

Test

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))

Galaretka , 13 12 10 bajtów

ḤRọ2ḂĠZFị@

Wykorzystuje to obserwację z mojej odpowiedzi w języku Python .

Wypróbuj online!

Jak to działa

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