A 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
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(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:
xas input, output
xas input, output the first
Infinitely output all of
If you want to take
x and output
x must be zero indexed.
This is code golf - shortest code in bytes wins. Standard loopholes are banned, as always.