[Question]
  [
A [half-exponential function](https://en.wikipedia.org/wiki/Half-exponential_function) is one which when composed with itself gives an exponential function. For instance, if `f(f(x)) = 2^x`, then `f` would be a half-exponential function. In this challenge, you will compute a specific half-exponential function.
Specifically, you will compute the function from the non-negative integers to the non-negative integers with the following properties:
* Monotonically increasing: if `x < y`, then `f(x) < f(y)`
* At least half-exponential: For all `x`, `f(f(x)) >= 2^x`
* Lexicographically smallest: Among all functions with the above properties, output the one which minimizes `f(0)`, which given that choice minimizes `f(1)`, then `f(2)`, and so on.
The initial values of this function, for inputs `0, 1, 2, ...` are:
`[1, 2, 3, 4, 8, 9, 10, 11, 16, 32, 64, 128, 129, 130, 131, 132, 256, 257, ...]`
You may output this function via any of the following methods, either as a function or as a full program:
* Take `x` as input, output `f(x)`.
* Take `x` as input, output the first `x` values of `f`.
* Infinitely output all of `f`.
If you want to take `x` and output `f(x)`, `x` must be zero indexed.
[Reference implementation](https://tio.run/##bZFNboMwEIX3nGKSla02iJ@qCxPSW3SDUGSldmOJTJBtkqiIs1MbKA1tvBnPm8/PM7ZujO17iXDkldyLW02QQWPUl6Cw2cG7OGyHbAdtAG5VwsKpsSDZfS2HizisiigDLLOBUxIQ8hwiaEEL22gECd1QkkVUuhPxEowfgbEHkyWYPAITD6YjKM8aFCiENAxxansykIUqp65meTTwug8bd@XTT29@dfPOjy73auTKbOHr5C3gP1ene1@SADfQvL7QsD5fiRqyNKFD9C/457ZpqqALAvczJ66Q0Pv35zdnauwHYwIvjHH9aQgN0R5JTMMGr5rXLq@5NoL8CtlsIN3x@b@d21SqtUJb4YqsW/bWrZ9BukIX9H2fRN8)
This is code golf - shortest code in bytes wins. [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are banned, as always.
  
[Answer]
## JavaScript (ES7), ~~51~~ 48 bytes
*Saved 3 bytes thanks to @Arnauld*
```
f=i=>i?f[f[q=f(i-1),r=f[i]||q+1]=(i>1)<<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)=>n?f(n-1,a,(n=2**a.indexOf(a.push(q)))<++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](https://codegolf.stackexchange.com/a/150067/42545) 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**—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—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)
[Answer]
# [Python 2](https://docs.python.org/2/), 60 bytes
```
d={};a=n=1
while 1:print a;a=d.get(n,a+1);d[1%n*a]=2**n;n+=1
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P8W2utY60TbP1pCrPCMzJ1XB0KqgKDOvRCERKJqil55aopGnk6htqGmdEm2omqeVGGtrpKWVZ52nbWv4/z8A "Python 2 – Try It Online")
Prints forever.
---
# [Python](https://docs.python.org/2/), 61 bytes
```
f=lambda n,i=2:n<1or(i>=n)*-~f(n-1)or(f(i)==n)<<i or f(n,i+1)
```
[Try it online!](https://tio.run/##Dcw7DoAgEIThq2zJ@iiW0oB3wSi6iQ6G2Nh4ddxyvkz@@32OAt9ajme6ljURBo1@QpBSnc4R3I1fdhiFDbJTjmYhKJVK5oP2wi3bACmoJuybE@HprorHavbh9gM "Python 2 – Try It Online")
A function. Outputs `True` in place of `1`.
[Answer]
# Perl 5, 53 + 1 (`-p`) = 54 bytes
```
$\=$_>0;map$a[$\=$a[$_]?2**$a[$_]:$\+1]=$_,++$\..$_}{
```
[Try it online](https://tio.run/##K0gtyjH9/18lxlYl3s7AOjexQCUxGsQDkvGx9kZaWhCWlUqMtmEsUJGOtrZKjJ6eSnxt9f//hub/8gtKMvPziv/rFgAA)
[Answer]
# Bash, 66 bytes
```
for((r=$1?2:1,i=2;i<=$1;i++));{ a[r=a[i]?2**a[i]:r+1]=$i;};echo $r
```
[Try it online](https://tio.run/##S0oszvj/Py2/SEOjyFbF0N7IylAn09bIOtMGyLPO1NbW1LSuVkiMLrJNjM6MtTfS0gLRVkXahrG2KpnWtdapyRn5CipF////NzQHAA)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 14 bytes
```
iL’2*»Ṁ‘$ṭ
⁸Ç¡
```
[Try it online!](https://tio.run/##ASYA2f9qZWxsef//aUzigJkyKsK74bmA4oCYJOG5rQrigbjDh8Kh//8xOA "Jelly – Try It Online")
### How it works
```
⁸Ç¡         Main link. No arguments.
⁸           Set the left argument and the return value to [].
 Ç¡         Read an integer n from STDIN and call the helper link n times, first on
            [], then on the previous result. Return the last result.
iL’2*»Ṁ‘$ṭ  Helper link. Argument: A (array)
 L          Take the length of A. This is the 0-based index of the next element.
i           Find its 1-based index in A (0 if not present).
  ’         Decrement to a 0-based index (-1 if not present).
   2*       Elevate 2 to the 0-based index.
      Ṁ‘$   Take the maximum of A and increment it by 1.
            Note that Ṁ returns 0 for an empty list.
     »      Take the maximum of the results to both sides.
         ṭ  Tack (append) the result to A.
```
[Answer]
# [Python 2](https://docs.python.org/2/), 111 bytes
```
def f(x):
 a=range(1,2**x)
 for i in range(1,x):a[i]=max(a[i],a[i-1]+1);a[a[i]]=max(a[a[i]],2**i)
 return a[:x]
```
[Try it online!](https://tio.run/##K6gsycjPM/r/PyU1TSFNo0LTiksh0bYoMS89VcNQx0hLq0KTSyEtv0ghUyEzTwEmDlSWGJ0Za5ubWKEBYugACV3DWG1DTevEaJAATArMBhmTCTSmKLWktChPITHaqiL2f0FRZl4J0EYjA83/AA "Python 2 – Try It Online")
This is a significant modification of [user202729](https://codegolf.stackexchange.com/users/69850/user202729)'s answer. I would have posted this improvement as a comment, but the answer is deleted and so comments are disabled.
[Answer]
# [Swift](https://swift.org), 137 bytes
```
func f(n:Int){var l=Array(1...n).map{$0>3 ?0:$0},p=8;if n>3{for i in 3..<n{if l[i]<1{l[i]=l[i-1]+1};if l[i]<n{l[l[i]]=p};p*=2}};print(l)}
```
Takes input as `Int` (integer) and prints as `[Int]` (integer array).
## Ungolfed version
```
func f(n:Int){
    var l = Array(1...n).map{$0 > 3 ? 0 : $0} // Create the range from 1 to n and set all
    var p = 8                                 // values greater than 3 to 0
    if n > 3 {
        for i in 3 ..< n {
            if l[i] < 1 {
                l[i] = l[i - 1] + 1
            }
            if l[i] < n {
                l[l[i]] = p
            }
            p *= 2
        }
    }
    print(l)
}
```
]