Quiero codificar de manera compacta enteros positivos xen bits, de manera que permita la decodificación de nuevo en los enteros originales para un decodificador sin estado que conozca el valor máximo mde cada uno x; será posible decodificar de manera única la concatenación de codificaciones, como es el caso en la codificación Huffman.
_{[La introducción anterior motiva al resto, pero no es parte de la definición formal]}

Notación: para cualquier número entero no negativo i, n(i)sea ​​el número de bits necesarios para representar ien binario; ese es el entero no negativo más pequeño ktal quei>>k == 0

  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..

Quiero una función F(x,m)definida para 0<xy x<=m, con salida una cadena de ' 0' o ' 1', que tenga estas propiedades:

1. F(x,m)tiene una longitud menor que 2*n(x)o 2*n(m)-1, la que sea menor.
2. Si x<yentonces:
   • F(x,m)no es más que F(y,m);
   • F(x,m)y F(y,m)difieren en alguna posición sobre la longitud de F(x,m);
   • Hay una entrada 0en F(x,m)la primera posición.
3. Cuando para ciertas mpropiedades 1 y 2 no se definen de manera única F(x,m)para todos los positivos xcomo máximo m, rechazamos cualquier codificación que proporcione una codificación más larga F(x,m)que alguna de otra manera aceptable, para la más pequeña xpara la que la longitud no coincide.

Nota: En lo anterior, de manera implícita, 0<x, 0<y, 0<m, x<=m, y y<=m, por lo que F(x,m)y F(y,m)se definen.

Se solicita el programa más corto que, dado cualquiera xy que mcumpla con las restricciones anteriores y hasta 9 dígitos decimales, arroje un resultado F(x,m)coherente con las reglas anteriores. El siguiente marco C (o su equivalente en otros lenguajes) no se cuenta:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line

Comentario: la propiedad 1 limita agresivamente la longitud codificada; la propiedad 2 formaliza que es posible una decodificación inequívoca y canonicaliza la codificación; Afirmo (sin pruebas) que esto es suficiente para definir de forma exclusiva la salida de Fcuando m+1es una potencia de dos, y que la propiedad 3 es suficiente para definir de manera única Fpara otro m.

Aquí hay una tabla parcial (hecha a mano; la primera versión publicada estaba plagada de errores, lo siento):

  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

Python 3, 163 bytes

n=int.bit_length
R=range
def F(x,m,c=0):
 for i in R(x):L=2*n(m)-2;D=1<<L;r=n(D-c-sum(D>>min(2*n(x+1)-1,L)for x in R(i+1,m)))-1;v=c;c+=1<<r
 return bin(v)[2:L+2-r]

Ignora el c=0parámetro, eso es un truco de golf.

Esto elige con avidez la representación más corta posible para cada número, sujeto a la condición de que los números restantes aún sean representables. Por lo tanto, por construcción, satisface exactamente las propiedades deseadas. Como resultado, en realidad no es tan difícil modificar este código para admitir un conjunto diferente de reglas de codificación.

Por ejemplo, aquí están las salidas hasta m=15:

m\x |   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
----+----------------------------------------------------------------------------------------------------------------------------
1   |   
2   |   0       1
3   |   0       10      11
4   |   0       10      110     111
5   |   0       10      110     1110    1111
6   |   0       100     101     110     1110    1111
7   |   0       100     101     1100    1101    1110    1111
8   |   0       100     101     110     11100   11101   11110   11111
9   |   0       100     101     110     11100   11101   11110   111110  111111
10  |   0       100     101     1100    1101    11100   11101   11110   111110  111111
11  |   0       100     101     1100    1101    11100   11101   111100  111101  111110  111111
12  |   0       100     101     1100    11010   11011   11100   11101   111100  111101  111110  111111
13  |   0       100     101     1100    11010   11011   11100   111010  111011  111100  111101  111110  111111
14  |   0       100     101     11000   11001   11010   11011   11100   111010  111011  111100  111101  111110  111111
15  |   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

Python, 171

def F(x,m):
 a=0;b=[9]
 while len(b)<m:
    if 4**len(bin(len(b)))*2>64*a<4**len(bin(m)):
     if(a&a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

Tenga en cuenta que las líneas que parecen comenzar con 4 espacios en realidad comienzan con una pestaña.

Pruebas, con el script de prueba de bitpwner:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)   0       
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      110      11100    11101    11110    11111   
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111  
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111  

Explicación:

Todo esto se basa en la observación de que entre dos elementos consecutivos del código, F (x, m) y F (x + 1, m), siempre agregamos uno al número binario, luego lo multiplicamos por dos algunas veces. Si se siguen estos pasos, entonces es un código válido. El resto simplemente prueba para asegurarse de que sea lo suficientemente corto.

Golfs: 175 -> 171: cambiado 2 ** (2 * ... a 4 **

Python - 370

Crea un árbol huffman, lo equilibra para ajustarse a las reglas, luego hace un recorrido por el árbol para obtener los valores finales.

def w(n,m,c,p=""):
    try:[w(n[y],m,c,p+`y`)for y in 1,0]
    except:c[n[0]]=p
d=lambda x:len(x)>1and 1+d(x[1])
v=lambda x,y:v(x[1],y-1)if y else x
def F(x,m):
    r=[m];i=j=0
    for y in range(1,m):r=[[m-y],r]
    while d(r)>len(bin(m))*2-6-(m==8):g=v(r,i);g[1],g[1][0]=g[1][1],[g[1][0],g[1][1][0]];i,j=[[i+1+(d(g)%2<1&(1<i<5)&(m%7<1)),j],[j+1]*2][d(g)<5]
    c={};w(r,m,c);return c[x]

Para una solución más sucinta que se base en el patrón emergente, mire la respuesta de Isaac.
Es un buen ejemplo de cómo un enfoque completamente diferente puede resolver el problema.

Prueba:

chars = 8
maxM = 15
print " "*chars,
for m in range(1,maxM+1):
    p = `m`
    print p+" "*(chars-len(p)),
print
for m in range(1,maxM+1):
    p = "F(x,"+`m`+")"
    print p+" "*(chars-len(p)),
    for x in range(1,maxM+1):
        try:
            q = `F(x,m)`[1:-1]
            print q+" "*(chars-len(q)),
        except:
            print
            break

Resultados:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)           
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      1100     1101     1110     11110    11111   
F(x,9)   0        100      101      1100     1101     1110     11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      11000    11001    11010    11011    11100    11101    11110    111110   111111  
F(x,13)  0        100      101      11000    11001    11010    11011    11100    11101    111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111