Half-Exponential Function

Question

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

This is code golf - shortest code in bytes wins. Standard loopholes are banned, as always.

• Nahuel Fouilleul: seems definition is not verified for 0 : f(f(0)) = f(1) = 2 but 2^0 = 1
• Nahuel Fouilleul: and for 1 : f(f(1)) = f(2) = 3 but 2^1 = 2
• Martin Ender: @NahuelFouilleul the requirement is f(f(x)) >= 2^x.
• Jeppe Stig Nielsen: Should we submit to OEIS?

Answer 1

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 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 2^j.

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

Normally the correct option is exactly 2^j. However, for the singular case i = 2, 2 exists in the array at index j = 1, which means that 2^j 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 2^j 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)

• izzyg: Note that inputs 272 and up give incorrect answers due to integer overflow issues. This is fine, as it works up to the limit of the datatype.
• user202729: Use 2** instead of 1<< hopefully fix the problem.
• user202729: Now the .99 kills the solution. But why using +.99 and not just +.9? What's the difference?
• ETHproductions: @user202729 I feel like an idiot--that was left in there from a previous version where I was using Math.log2(...) and had to calculate the ceiling. Now it's not needed at all. Thanks! I'll look into the 2** thing--I was using 2**...+.99|0 originally, but 1<< was shorter because I didn't need the |0. Now I think there's no difference...

Answer 2

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

Prints forever.

---

Python, 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!

A function. Outputs True in place of 1.

Answer 3

Perl 5, 53 + 1 (-p) = 54 bytes

$\=$_>0;map$a[$\=$a[$_]?2**$a[$_]:$\+1]=$_,++$\..$_}{

Try it online

Answer 4

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

Answer 5

Jelly, 14 bytes

iL’2*»Ṁ‘$ṭ
8Ç¡

Try it online!

How it works

8Ç¡ Main link. No arguments.
8 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 6

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

This is a significant modification of user202729's answer. I would have posted this improvement as a comment, but the answer is deleted and so comments are disabled.

• izzyg: This fails with a "list index out of range" exception on the input 258. I think the problem is that x**2 is too small.
• user202729: Well... Python 2 is different (often less bytes) from Python 3.
• user202729: As expected, half-exponential is way larger than quadratic. The solution get "list index out of range" at x=1000. You may want to try 2**x - terribly large, but codegolf is codegolf.
• notjagan: @user202729 Ah, this is true. Unfortunately it now encounters an entirely different problem with larger inputs in that 2**x creates far too large of a range for Python to continue.

Answer 7

Swift, 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)
}

• ETHproductions: I'm curious, what will happen if you remove the space before the ??
• Endenite: @ETHproductions That leads to a compiler error, since integers can't be optional chained.