Half-Exponential Function
JavaScript (ES7), 51 48 bytes

Saved 3 bytes thanks to @Arnauld

f=i=&gt;i?f[f[q=f(i-1),r=f[i]||q+1]=(i&gt;1)&lt;&lt;i,i]=r:1


Takes in n and outputs the n'th item in the sequence.



JavaScript (ES7), 70 68 64 bytes

f=(n,a=[],q=1)=&gt;n?f(n-1,a,(n=2**a.indexOf(a.push(q)))&lt;++q?q:n):a


A recursive function that takes in x and returns the first x items of the sequence as an array.

How it works

The array a is procedurally generated, one item at a time, until it reaches the desired length. (A port of the infinite technique used in xnor's excellent Python answer would likely be shorter.)

We can make the following observation for each index i (0-indexed):


If i exists as an item in a at index j (a[j] = i), then a[i] needs to be at least 2j.


This is true because f(f(j)) needs to be at least 2j, and f(f(j)) is equivalent to a[a[j]], which is in turn equivalent to a[i].

Normally the correct option is exactly 2j. However, for the singular case i = 2, 2 exists in the array at index j = 1, which means that 2j would be 2&mdash;but this means that we would have 2 at both a[1] and a[2]. To get around this, we take the maximum of 2j and a[i-1] + 1 (one more than the previous item), which gives 3 for i = 2.

This technique also happens to take care of deciding whether or not j exists&mdash;if it doesn't, JS's .indexOf() method returns -1, which leads to taking the max of a[i-1] + 1 and 2-1 = 0.5. Since 
all items in the sequence are at least 1, this will always return the previous item plus one.

(I'm writing this explanation late at night, so please let me know if something is confusing or I missed anything)