Yet Unused Pairs

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 nth term in this sequence.

This is code-golf so you should aim to minimize the size of your source code as measured in bytes.

OEIS A036552

Answer 1

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 2

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 3

Python 3, 80 72 69 bytes

^{-7 bytes thanks to Mr. Xcoder!}

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

Try it online!

Answer 4

Jelly, 15 bytes

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

Try it online!

Answer 5

Mathics, 56 53 bytes

^{-3 bytes thanks JungHwan Min!}

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

Try it online!

Based on the Mathematica expression given in the OEIS link.

Answer 6

PHP, 64 bytes

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

Try it online!

PHP, 77 bytes

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

Try it online!

PHP, 78 bytes

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

Try it online!

Answer 7

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

Answer 8

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.

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

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 9

Python 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!

Background

Every positive n integer can be expressed uniquely as n = 2^o(n)c(n), where c(n) is odd.

Let ⟨a_n⟩_n>0 be the sequence from the challenge spec.

We claim that, for all positive integers n, o(a_2n-1) is even. Since o(a_2n) = o(2a_2n-1) = o(a_2n-1) + 1, this is equivalent to claiming that o(a_2n) is always odd.

Assume the claim is false and let 2m-1 be the first odd index of the sequence such that o(a_2m-1) is odd. Note that this makes 2m be the first even index of the sequence such that o(a_2m-1) is even.

o(a_2m-1) is odd and 0 is even, so a_2m-1 is divisible by 2. By definition, a_2m-1 is the smallest positive integer not yet appearing in the sequence, meaning that a_2m-1/2 must have appeared before. Let k be the (first) index of a_2m-1/2 in a.

Since o(a_k) = o(a_2m-1/2) = o(a_2m-1) - 1 is even, the minimality of n implies that k is odd. In turn, this means that a_k+1 = 2a_k = a_2m-1, contradicting the definition of a_2m-1.

How it works

yet to come

Answer 10

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

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 11

Haskell, 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!

This one abuses Haskell's lazy evaluation to the fullest extent.

Answer 12

Perl 6, 50 bytes

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

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 13

k, 27 bytes

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

1-indexed. Try it online!

Using (!y)^x instead of &^x?!y works too.

Answer 14

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!

Answer 15

C# (Visual C# Interactive Compiler), 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!

-6 bytes thanks to @ASCIIOnly!

Answer 16

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!

Answer 17

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 nth item, 1-indexed.

Answer 18

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 19

Ruby, 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!

Answer 20

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 21

Jelly, 13 12 10 bytes

ḤRọ2ḂĠZFị@

This uses the observation from my Python answer.

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 22

Husk, 18 bytes

!ṁSeDfȯ¬%2öL→x1ḋḣ¹

Try it online!

Same method as the 05AB1E solution from Emigna.

Both are 1-indexed.

Husk, 19 bytes

!!¡S+ȯSeD←S-ȯḣ→▲ḣ2¹

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