¿Convertir un par de números enteros en un número entero, de forma óptima?

Question

¿Cuál es el mejor algoritmo que toma dos enteros positivos $a,b$ y devuelve un número entero positivo $c$ tal que todos $c$ ' $(a,b)$ se distingue de $(b,a)$ donde el mejor significa que la longitud de $c$ ¿en términos de dígitos es el más corto posible, por término medio?

Esto implica que podemos calcular $a,b$ de $c$ con el mismo algoritmo. (invirtiéndolo)

Si tenemos un límite $x$ tal que $a,b\le x$ alors $f(a,b)$ tiene $x^2$ valores únicos, lo que significa que nuestro $c$ debe tomar valores de $[1,x^2]$ para tener la menor cantidad de dígitos, lo que puede lograrse con la siguiente función:

$$f(a,b)=(a-1)x+b$$

Si $x$ no existe, ¿cuál es entonces el algoritmo óptimo?

(Para que tenga sentido qué algoritmo es el más corto, estaba comparando la longitud del $c$ con la suma de las longitudes de $a,b$ y calculando la media, que es más precisa cuantos más valores consideremos).

---

Hasta ahora tenía dos ideas;

$(1)$ Factorización

Tome los factores de $a$ y $b$ . Ahora puede utilizar la segunda secuencia más larga de $0$ s como separador entre factores, y la secuencia más larga de $0$ s como separador entre los factores de los dos números.

Por ejemplo: $f(123,1007)=(3\times41 ),( 19\times53)=30410019053$

Por ejemplo: $f(30,1006)=(2\times3\times5),(2\times503)=2003005000200503$

Pero esto puede optimizarse, para casos como $f(2^{64},3^{64})$ e incluso así, parece que son demasiados dígitos extra.

$(2)$ Ceros finales

Toma $a$ , invierte sus dígitos y pon un dígito aleatorio delante del primer dígito. De este modo, el resultado no tendrá ceros al final. A continuación, utilice la secuencia más larga de $0$ s como separador de $b$ .

Ejemplo: $f(123,456)=93210456$

Ejemplo: $f(123,10100)=932100010100$

Ejemplo: $f(420,314)=902400314$

Esto también tiene margen de optimización si analizamos casos concretos y añadimos normas más específicas. Pero parece que ni siquiera entonces será óptimo.

Supongo que la solución óptima pasaría por estudiar un par o más de casos por separado.

Answer 1

Una posibilidad es $$f(a,b) = \frac12 (a+b-2)(a+b-1) + a$$ que básicamente ordenan los puntos $(a,b) \in \mathbb{Z}_{+}^2$ primero por $a+b$ y luego por $a$ .

$$\begin{bmatrix} f(1,1) & f(1,2) & f(1,3) &\cdots\\ f(2,1) & f(2,2) & f(2,3) &\cdots\\ f(3,1) & f(3,2) & f(3,3) & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} 1 & 2 & 4 & \cdots\\ 3 & 5 & 8 & \cdots\\ 6 & 9 & 13 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} $$ No es tan difícil calcular la inversa de $f(a,b)$ . Dejaré la diversión para ti.

Answer 2

En Función de emparejamiento de Cantor cubre bien los enteros no negativos. Como biyección, utiliza todos los valores objetivo para $f(a,b)$ Así que no se puede ser más eficiente que eso. El valor de la función de emparejamiento es aproximadamente $\frac 12(a+b)^2$ . Para manejar enteros, basta con componerlo con una biyección entre los enteros y los naturales: $$g(n)=\begin {cases} 2n& n \ge 0\\-2n-1 & n \lt 0 \end {cases}$$ a continuación, utilice la función de emparejamiento en los naturales resultantes.

Answer 3

Aquí hay algo que debería funcionar: Dado $a$ y $b$ , dejemos que $h$ sea el número de dígitos de $a$ , $k$ sea el número de dígitos de $b$ y $n=h+k$ el número total de dígitos. Escribe primero $n$ alors $h$ alors $n$ $0$ 's, entonces $k$ alors $a$ alors $b$ . Por ejemplo

$$f(13,47)=42000021347\quad\text{while}\quad f(134,7)=43000011347$$

Para ir de $c$ volver a $(a,b)$ cuente el número de dígitos en $c$ y luego quita el mayor número del principio que sea menor que ese. Por ejemplo, del $11$ -número de dígitos $42000021347$ se obtiene $4$ no $42$ . Eso te dice que la concatenación es $ab=1347$ dejando $200002$ para ser la concatenación del número de dígitos en $a$ y $b$ individualmente, con $4$ $0$ 's en el medio.

Probablemente pueda arreglárselas con menos de $n$ $0$ 's. Mi primer intento no tenía ninguna, por ejemplo, $g(13,47)=4221347$ pero entonces me di cuenta de que puedes encontrarte con ambigüedades, tales como

$$g(12345678910,1)=g(1,23456789101)=12111123456789101)$$

donde no está claro si $12=11+1$ o $1+11$ .

Answer 4

Necesitamos simetría para $(a,b)=(b,a)$ . Una forma podría ser almacenar binarios $a+b,a\oplus b$ que es inclusivo y exclusivo o de bits. Ambos son simétricos. Si necesitamos mapear a base 10 podemos primero convertir a decimal codificado en binario.

¿Puede alguien ayudarme a demostrar que funciona? Debería ser posible mediante una pequeña tabla lógica que demuestre que cualquier combinación de or y xor sólo da una combinación posible a y b.