21
2
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
, thenf(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 minimizesf(1)
, thenf(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, outputf(x)
.Take
x
as input, output the firstx
values off
.Infinitely output all of
f
.
If you want to take x
and output f(x)
, x
must be zero indexed.
This is code golf - shortest code in bytes wins. Standard loopholes are banned, as always.
seems definition is not verified for 0 : f(f(0)) = f(1) = 2 but 2^0 = 1 – Nahuel Fouilleul – 2017-12-07T11:43:42.410
and for 1 : f(f(1)) = f(2) = 3 but 2^1 = 2 – Nahuel Fouilleul – 2017-12-07T11:49:18.610
1@NahuelFouilleul the requirement is f(f(x)) >= 2^x. – Martin Ender – 2017-12-07T12:10:09.600
1
Should we submit to OEIS?
– Jeppe Stig Nielsen – 2017-12-07T13:53:58.577