[Question]
  [
Let's define a sequence of positive integers. We will define the value of the sequence at every even index to be double the previous term. The odd indices of the sequence will be smallest positive integer not yet appearing in the sequence.
Here are the first couple terms.
```
1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30
```
You can also think of this as the list of concatenated pairs **(n,2n)** where **n** is the least unused positive integer so far.
## Task
Given a number **n** as input calculate the **n**th term in this sequence.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so you should aim to minimize the size of your source code as measured in bytes.
[OEIS A036552](http://oeis.org/A036552)
  
[Answer]
## Haskell, 40 bytes
```
l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)
```
Zero-based. `l` incrementally builds the sequence from a lazy list of remaining integers.
[Answer]
## 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={})
```
### How?
We keep track of:
* The last inserted value ***b***.
* All previously encountered values in the lookup table ***a***.
Internally, we're using a 0-based index ***i***. Odd and even behaviors are therefore inverted:
* At odd positions, the next value is simply `2 * b`.
* At even positions, we use the recursive function ***g()*** and the lookup table ***a*** to identify the smallest matching value:
```
(g = k => a[k] ? g(k + 1) : k)(1)
```
To save a few bytes, ***i*** is initialized to `{}` rather than `0`. This compels us to use:
* `i^n` to compare ***i*** with ***n*** because `({}) ^ n === n` whereas `({}) - n` evaluates to `NaN`.
* `-~i` to increment ***i***, because `({}) + 1` would generate a string.
### Demo
```
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));
}
```
[Answer]
# [Python 3](https://docs.python.org/3/), 80 72 69 bytes
-7 bytes thanks to [Mr. Xcoder](https://codegolf.stackexchange.com/users/59487/mr-xcoder)!
```
f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]
```
[Try it online!](https://tio.run/##LcoxCoQwEEbhq6QRZmIsotgIexKxGNFowPwGN80inj0r6CsfX/yldUeTs/tsEsZJFDoowdQ7QmVZ1yZ40KkPwTITSstXdeogkZx5H/PFQ4@iHnI8PBJt/pvoIeox1ijb8l3@Aw "Python 3 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 15 bytes
```
Jḟ⁸ḢðḤṭṭ
0Ç¡Ḋị@
```
[Try it online!](https://tio.run/##AS0A0v9qZWxsef//SuG4n@KBuOG4osOw4bik4bmt4bmtCjDDh8Kh4biK4buLQP///zU "Jelly – Try It Online")
[Answer]
# [Mathics](http://mathics.github.io/), 56 53 bytes
-3 bytes thanks [JungHwan Min](https://codegolf.stackexchange.com/users/60043/junghwan-min)!
```
(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&
```
[Try it online!](https://tio.run/##y00sychMLv6fZvtfo9y2utbaJT@6vM6tKDU1sC5bTQ0oVl7nlZ@ZV1edrWOUXaupA6SVa2Oty6OjlWNjNdX@BxRl5pVEpynoOygEJealp0Yb6igYmsXG/gcA "Mathics – Try It Online")
Based on the Mathematica expression given in the OEIS link.
[Answer]
# [PHP](https://php.net/), 64 bytes
```
for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;
```
[Try it online!](https://tio.run/##K8go@G9jX5BRwKWSWJSeZ6tkqWT9Py2/SMMazNdVydTWttbMTNNQyVRTUUm1NdSESFYD2draKnm11prWqTnFqSqpWrZG1qnJGfkqqdb//wMA "PHP – Try It Online")
# [PHP](https://php.net/), 77 bytes
```
for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;
```
[Try it online!](https://tio.run/##HcpBCoMwEEbhvcfQn5KYdlF3MoYepBQJZTQDEoepm54@pS4f39OsdXpo1gbJ1hLbsaW67Obo7BskBII9XxHsZXGQy92fLmVOZunrwDEElCvMkyfePgzu40D8zjuYaqcm5ZjN/Yf6Aw "PHP – Try It Online")
# [PHP](https://php.net/), 78 bytes
```
for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;
```
[Try it online!](https://tio.run/##HccxDsIwDADAnWcUC9m0DGWjJspDqqqKqNN4SS2LhdcHxHQ6K9ae0YqdIPleQ/fouOXDkf@/gfY9E0gAn5cAehmj1A2Te/qsm@aMnuouCDqMNIDHaV6IpvsVhOVVjh/tbK71vTqCE7cv "PHP – Try It Online")
[Answer]
# 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;
```
[Try it online](http://sandbox.onlinephpfunctions.com/code/2b919bcdf58b06055846cc4c3ea4a5cf8d860522)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~16~~ ~~15~~ 14 bytes
1-indexed.  
Uses the fact that the binary representation of elements at odd indices in the sequence ends in an even number of zeroes: [A003159](http://oeis.org/A003159).
```
Lʒb1¡`gÈ}€x¹<è
```
[Try it online!](https://tio.run/##ASEA3v8wNWFiMWX//0zKkmIxwqFgZ8OIfeKCrHjCuTzDqP//MTY "05AB1E – Try It Online")
**Explanation**
```
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)
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~59~~ ~~51~~ 49 bytes
```
f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)
```
[Try it online!](https://tio.run/##FcyxDoIwFEbhWZ/iXyr3Qhtp2UjwXWqkSKoX0sDAwqvXOp5vOOuxvRdxOYfh47/Pl4foOLje3UWZriZrIi8JgaQ5Kd5KFdaxsZxDccEsSF6mkayGbVvur5c1zbKhUm6HeUB1ewUFEv2/MOcf "Python 2 – Try It Online")
### Background
Every positive **n** integer can be expressed uniquely as **n = 2o(n)c(n)**, where **c(n)** is odd.
Let **⟨an⟩n>0** be the sequence from the challenge spec.
We claim that, for all positive integers **n**, **o(a2n-1)** is even. Since **o(a2n) = o(2a2n-1) = o(a2n-1) + 1**, this is equivalent to claiming that **o(a2n)** is always odd.
Assume the claim is false and let **2m-1** be the first odd index of the sequence such that **o(a2m-1)** is odd. Note that this makes **2m** be the first even index of the sequence such that **o(a2m-1)** is even.
**o(a2m-1)** is odd and **0** is even, so **a2m-1** is divisible by **2**. By definition, 
**a2m-1** is the *smallest positive integer not yet appearing in the sequence*, meaning that **a2m-1/2** must have appeared before. Let **k** be the (first) index of **a2m-1/2** in **a**.
Since **o(ak) = o(a2m-1/2) = o(a2m-1) - 1** is even, the minimality of **n** implies that **k** is odd. In turn, this means that **ak+1 = 2ak = a2m-1**, contradicting the definition of **a2m-1**.
### How it works
*yet to come*
[Answer]
# [R](https://www.r-project.org/), ~~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]}
```
[Try it online!](https://tio.run/##K/qfZvs/rTQvuSQzP08jT7M6Lb9II1MhM0/BSMvQKk/TLTpT19DKINa2PCMzOUNDESimmpmn6qYZbRgLVGDE5RadF1v7vzixoCCnUgMoYKCTpsmVpmGo@R8A "R – Try It Online")
An anonymous function that takes one argument. `F` defaults to `FALSE` or `0` so that the algorithm correctly assesses that no positive integers are in the sequence yet.
The algorithm generates the pairs in a `for` loop in the following manner (where `i` goes from `2` to `2n` by `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
```
[Answer]
# [Haskell](https://www.haskell.org/), 63 bytes
```
g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P12hwjbaSCtdo0LXUFMnOrEm0UY32lBPL1YnMSEvv8Q1JzU3ITexQCEdJAhUExurqGgAxLn5KQoVCkb/cxMz82wLijLzSlRKErNTFYwMVODKY/8DAA "Haskell – Try It Online")
This one abuses Haskell's lazy evaluation to the fullest extent.
[Answer]
# [Perl 6](http://perl6.org/), 50 bytes
```
{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/WsNQp9ohXtXI3t5IyyE@WkvXMFZRMS2zqLhEQetRR6dDvI6hnp5WrR6Q0IxWiY@t/W@tUJxYqZCbWAA0QUchzsjA@j8A "Perl 6 – Try It Online")
* `1, { ... } ... *` is a lazily-generated infinite sequence where each term after the first is provided by the brace-delimited code block. Since the block references the `@_` array, it receives the entire current sequence in that array.
* If the current number of elements is odd (`@_ % 2`), we're generating an even-indexed element, so the next element is double the last element we have so far: `2 * @_[*-1]`.
* Otherwise, we get the first positive integer that does not yet appear in the sequence: `first * ∉ @_, 1..*`.
* `$_` is the argument to the outer function. It indexes into the infinite sequence, giving the function's return value.
[Answer]
# [k](https://en.wikipedia.org/wiki/K_(programming_language)), 27 bytes
```
*|{x,*(&^x?!y;|2*x)2!y}/!2+
```
1-indexed. [Try it online!](https://tio.run/##y9bNz/7/P81Kq6a6QkdLQy2uwl6x0rrGSKtC00ixslZf0Uj7vwZXmoOhAVeauqG2ohGYNjDQVgSKaP4HAA "K (oK) – Try It Online")
Using `(!y)^x` instead of `&^x?!y` works too.
[Answer]
# Mathematica, 82 bytes
```
(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&
```
[Try it online!](https://tio.run/##y00sychMLv6fZvtfo9i2utY60dbQOs1W2To8IzMnNTrNzkDHMy26uM6tKDU1sC5Rp7jOsaAgNS8lJL@uOlHHKLE21jpRW9s6TVc31totJ7GkJDUvujg2Olo5NlZT7X9AUWZeiYJDmoKDkcF/AA "Mathics – Try It Online")
[Answer]
# [C# (Visual C# Interactive Compiler)](http://www.mono-project.com/docs/about-mono/releases/5.0.0/#csc), 82 bytes
```
x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}
```
[Try it online!](https://tio.run/##FYwxC4MwEEb3/orjpsSrRR17XpZCp@6dRRRuiZDEEin97WkcvuF78N4c2zlqee5@HtWna52DFaRkcd964JCe1y2YzxQgCiJnN3BuZbAnjSRDcxDekePtsfk0qY@GqCK0bDksaQ8ecnPwr/DlVM6o1qiO0ncdK5G9ALyDpuWlfjFKCOIAaTVqLZc/ "C# (Visual C# Interactive Compiler) – Try It Online")
-6 bytes thanks to @ASCIIOnly!
[Answer]
# JavaScript, 51 bytes
After golfing this down, it pretty much turned into edc65's solution.
```
n=>(g=x=>g[++x]?g(x):(g[y=x*2]=--n)?--n?g(x):y:x)``
```
[Try it online!](https://tio.run/##JcixCoMwEADQX3HocNcQKYKL9vQjOoqQoCa0yJ3EIJHSb08LXd7wXvaw@xSeW9Qs85IdZaYOPCXq/KBUGnsPCRvww0npWo2kNWP/4/9nk9CY7CQA063le1W3OAnvsi7lKh7M5a0UfwoqTLnZ@RFtiFCjcsCI@Qs)
[Answer]
## 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))))%)
```
Iterates `n` times to build up the sequence and returns the `n`th item, 1-indexed.
[Answer]
# Ruby, 60 bytes
```
->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}
```
0-indexed. We loop `n/2+1` times, generating two values each time and storing them by populating an array at their indices. `v+v*n%2` gives the output, either `v` or `v*2` depending on the parity of `n`.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 49 bytes
```
->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}
```
Start with [0], add pairs to the array until we have at least n+1 elements, then take the n+1th (1-based)
[Try it online!](https://tio.run/##KypNqvyfZvtf1y6vWqvYtsTWwLq4JrpE29Yw1ta2uKam2MamBIi0jErzSjJzFIqj82KtQUTtf2MDvZLM3NTi6prMmoLSkmKFtOhMoDAA "Ruby – Try It Online")
[Answer]
# JavaScript (ES6), 60 ~~65~~ bytes
An iterative solution.
```
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")
```
*Less golfed*
```
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))
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13~~ ~~12~~ 10 bytes
```
ḤRọ2ḂĠZFị@
```
This uses the observation from [my Python answer](https://codegolf.stackexchange.com/a/132217/12012).
[Try it online!](https://tio.run/##ASoA1f9qZWxsef//4bikUuG7jTLhuILEoFpG4buLQP8xMDBSwrXFvMOH4oKsR/8 "Jelly – Try It Online")
### How it works
```
Ḥ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.
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 18 bytes
```
!ṁSeDfȯ¬%2öL→x1ḋḣ¹
```
[Try it online!](https://tio.run/##ASkA1v9odXNr//8h4bmBU2VEZsivwqwlMsO2TOKGkngx4biL4bijwrn///8yOA "Husk – Try It Online")
Same method as the 05AB1E solution from Emigna.
Both are 1-indexed.
# [Husk](https://github.com/barbuz/Husk), 19 bytes
```
!!¡S+ȯSeD←S-ȯḣ→▲ḣ2¹
```
[Try it online!](https://tio.run/##yygtzv7/X1Hx0MJg7RPrg1NdHrVNCNY9sf7hjsWP2iY9mrYJyDA6tPP///9GFgA "Husk – Try It Online")
Uses infinite iteration to generate the sequence.
## Explanation
```
!!¡S+ȯSeD←S-ȯḣ→▲ḣ2¹
                ḣ2  array [1,2]
  ¡                 apply function repeatedly on array, yielding intermediate results
   S                hook: S f g x = s f x (g x)
    +               f → list addition
     ȯ              g → compose 3: ȯ f g h x = f (g (h x))
      S                 f → hook: S f g x = s f x (g x)
       e                    f → list of two elements
        D                   g → number doubled
         ←              g → decrement
          S             h → hook: S f g x = s f x (g x)
           -                f → list subtraction
            ȯ               g → compose 3: ȯ f g h x = f (g (h x))
             ḣ                  f → range 1..n
              →                 g → increment
               ▲                h → maximum
                    altogether, this appends the first element of
                    1..max+1 not in the array,
                    and it's double.
 !                  take the nth result
!                   take the nth value
```
]