Hoy, calcularemos la función binaria más eficiente. Más específicamente, calcularemos la función que, cuando se crea una expresión aplicando la función a la entrada constante 0 o su propia salida, puede representar todos los enteros positivos con las expresiones más cortas posibles, dando mayor prioridad a los enteros más pequeños.

Esta función se construye de la siguiente manera:

Para cada número entero, comenzando en 1 y yendo hacia arriba, elija la expresión más corta a la que aún no le hemos asignado una salida, y haga que ese entero sea la salida de esa expresión. Los lazos en la longitud de la expresión se romperán con un argumento izquierdo más pequeño y luego con un argumento derecho más pequeño. Así es como funciona:

• Inicialmente, 1 no está asignado. La expresión sin asignar más corta es f(0, 0), por lo que la estableceremos en 1.

• Ahora, 2 no está asignado. Las expresiones sin asignar más cortas son f(f(0, 0), 0)= f(1, 0)y f(0, f(0, 0))= f(0, 1). Los lazos se rompen hacia la izquierda argumento más pequeño, por lo que f(0, 1) = 2.

• La expresión sin asignar más corta que queda es f(f(0, 0), 0)= f(1, 0), entonces f(1, 0) = 3.

• Ahora, estamos sin expresiones con solo 2 fsy 3 0s, por lo que tendremos que agregar uno más de cada uno. Romper los lazos por argumento izquierdo, luego argumento derecho, obtenemos f(0, 2) = 4, desde entonces f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

• Continuando, tenemos f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Aquí hay una tabla que completé para los primeros valores:

    0  1  2  3  4  5  6  7  8
 /---------------------------
0|  1  2  4  5  9 10 11 12 13
1|  3  6 14 15 37 38 39 40 41
2|  7 16 42 43
3|  8 17 44 45
4| 18 46
5| 19 47
6| 20 48
7| 21 49
8| 22 50

Otra forma de verlo es que cada salida tiene un tamaño, igual a la suma de los tamaños de sus entradas más uno. La tabla se completa en orden de tamaño creciente de salida, los vínculos se rompen al minimizar la entrada izquierda y luego la entrada derecha.

Su desafío es, dados dos enteros no negativos como entrada, cálculo y salida del valor de esta función. Este es el código de golf. La solución más corta, en bytes, gana. Las lagunas estándar están prohibidas.

Haskell, 110 bytes

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n<-[0..k],a<-c!!n,b<-c!!(k-n)]|k<-[0..]],(p,i)<-zip(concat c)[0..],p==q]

El argumento aquí se toma como la tupla (x,y). Bastante similar a la respuesta anterior, pero la lista de búsqueda contiene solo los pares de índices izquierdo y derecho en lugar de los árboles.

Python 3, 154 bytes

b=lambda n:[(l,r)for k in range(1,n)for l in b(k)for r in b(n-k)]+[0]*(n<2)
def f(x,y):r=sum((b(n)for n in range(1,x+y+3)),[]);return r.index((r[x],r[y]))

No es muy rápido ni muy golfista, pero es un comienzo.

¡Guauu! Realmente logré hacer un algoritmo de computación eficiente. No esperaba esto al principio. La solución es bastante elegante. En repetidas ocasiones deduce más y más, luego recurre hasta el caso base de 0. En esta respuesta, la función C (n) denota los números catalanes .

El primer paso crucial es reconocer que hay C (0) = 1 valores de longitud cero (es decir, 0 en sí mismo), C (1) = 1 valores de longitud uno (es decir, f (0, 0)), C (2) = 2 valores de longitud dos (f (0, f (0, 0)) yf (f (0, 0), 0)).

Esto significa que si estamos buscando la enésima expresión, y encontramos la k más grande tal que C (0) + C (1) + ... + C (k) <= n, entonces sabemos que n tiene longitud k .

¡Pero ahora podemos continuar! Debido a que la expresión que buscamos es la expresión n - C (0) - C (1) - ... - C (k) th en su clase de longitud.

Ahora podemos usar un truco similar para encontrar la longitud del segmento izquierdo, y luego el rango dentro de esa subsección. ¡Y luego volvemos a esos rangos que encontramos!

Encontró que f (5030, 3749) = 1542317211 en un abrir y cerrar de ojos.

Python, sin competencia

def C(n):
    r = 1
    for i in range(n):
        r *= 2*n - i
        r //= i + 1
    return r//(n+1)

def unrank(n):
    if n == 0: return 0

    l = 0
    while C(l) <= n:
        n -= C(l)
        l += 1

    right_l = l - 1
    while right_l and n >= C(l - 1 - right_l) * C(right_l):
        n -= C(l - 1 - right_l) * C(right_l)
        right_l -= 1

    right_num = C(right_l)

    r_rank = n % right_num
    l_rank = n // right_num

    for sz in range(l - 1 - right_l): l_rank += C(sz)
    for sz in range(right_l): r_rank += C(sz)

    return (unrank(l_rank), unrank(r_rank))

def rank(e):
    if e == 0: return 0
    left, right = e

    l = str(e).count("(")
    left_l = str(left).count("(")
    right_l = str(right).count("(")
    right_num = C(right_l)

    n = sum(C(sz) for sz in range(l))
    n += sum(C(sz)*C(l - 1 - sz) for sz in range(left_l))

    n += (rank(left) - sum(C(sz) for sz in range(left_l))) * C(right_l)
    n += rank(right) - sum(C(sz) for sz in range(right_l))

    return n

def f(x, y):
    return rank((unrank(x), unrank(y)))

Estoy bastante seguro de que estoy haciendo un montón de cálculos innecesarios y se pueden eliminar muchos pasos intermedios.