# Yet Unused Pairs

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.

Given a number n as input calculate the nth term in this sequence.

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

OEIS A036552

• May we choose to use either 0- or 1-indexing? Jul 12 '17 at 15:01
• @notjagan Sure go ahead. Jul 12 '17 at 15:02
• The 2-adic valuation of odd elements of the series is always even. Might be useful to someone. Jul 12 '17 at 15:57

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.

## JavaScript (ES6), 92826967 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));
}

• 60 bytes Jan 5 '19 at 10:17

# Python 3, 8072 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!

• You can repace set(...) with {*...} for 78 bytes Jul 12 '17 at 15:10
• @Zacharý Were you reffering to my comment? If so, a set in Python 3 can be {*...} instead of set(...). Jul 12 '17 at 15:12
• I was commenting without thinking, I realized a few moments later that {...for...in...} woould be more byes. Jul 12 '17 at 15:13
• Actually, it would save 4 bytes, because you use it twice Jul 12 '17 at 15:13
• 69 bytes. (and it doesn't use True for 1) Jul 12 '17 at 15:20

# Jelly, 15 bytes

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


Try it online!

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

• Also 53 bytes: Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]& Jul 12 '17 at 16:32
• 45 bytes in Mathematica since Mathics seems to handle empty Sequences (and maybe Set too?) differently.
– att
Sep 1 at 17:30

for(;$argn-$i++;)if($i&$$e=1)for(;{e=++n};);elsee*=2;echoe;  Try it online! # PHP, 77 bytes for(;argn-i++;r[]=e)if(i&1)for(;in_array(e=++n,r););elsee*=2;echoe;  Try it online! # PHP, 78 bytes for(;argn-i++;)e=r[]=i&1?end(array_diff(range(i,1),r?:[])):2*e;echoe;  Try it online! # 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

# 05AB1E, 1615 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)


# Python 2, 5951 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 = 2o(n)c(n), where c(n) is odd.

Let ⟨ann>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.

yet to come

# R, 7069 65 bytes

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)*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)     # 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


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


Try it online!

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

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

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

• In oK you could even use y^x instead to save three bytes Sep 1 at 18:09

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

• 58 bytes in Mathematica (although I should probably just post a separate answer since the idea is pretty different). Jul 12 '17 at 15:26
• Did you copy that from OEIS link? Jul 12 '17 at 15:48
• I modified it to fit the task and to be golfed more, but it more or less is the same as the OEIS link. Jul 12 '17 at 15:50
• @not post a new answer if you want and credit the author Jul 12 '17 at 15:55

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

• C#8 may be too new to be common on online interpreters for now, added to the fact that csi is a Mono thing so you'd have to wait for Mono to implement it and add it to a stable build (if it hasn't already) Jan 6 '19 at 7:33
• sadly it isn't easy to check for this in C# Jan 6 '19 at 8:12
• Use this to start? But yeah, doesn't seem like a straightforward thing. docs.microsoft.com/en-us/dotnet/api/…
– dana
Jan 6 '19 at 8:16
• 86? - don't think the :s are needed since it will be the largest number in the list Jan 6 '19 at 8:22
• Also 2.0 => 2f
– dana
Jan 6 '19 at 8:23

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

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

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

# Ruby, 49 bytes

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


Start with , add pairs to the array until we have at least n+1 elements, then take the n+1th (1-based)

Try it online!

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

# Jelly, 1312 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.


# 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)
ȯ              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
`