¿Existe una función explícita de mapeo $2^n+2^m$ a $(n,m)$ ?

Question

Sabemos que el número $2^n+2^m$ es único para $n,m\in\mathbb{N}$ . ¿Hay alguna forma explícita de escribir una función $\sigma:\mathbb{N}\to\mathbb{N}^2$ tal que $$ \sigma(2^n+2^m)=(n,m), $$ para todos $n,m\in\mathbb{N}$ ?

Observación (edición): Aquí, $(n,m)$ debe interpretarse como el par desordenado $\{n,m\}$ , ya que sólo me interesa la pareja. Más concretamente, quiero encontrar funciones $\sigma,f$ y $g$ tal que $$ \sigma(k)=(g(k),f(k)), $$ donde $k=2^{g(k)}+2^{f(k)}$ , $\forall k \in\mathbb{N}$ .

Answer 1

¿Qué opina de $$\forall k \in \mathbb{N}, \quad \sigma(k)=\left( \lfloor \log_2(k) \rfloor, \lfloor \log_2 \left( k-2^{\lfloor \log_2(k) \rfloor} \right)\rfloor \right)$$

Esto está bien definido excepto cuando $k$ es una potencia de $2$ .

En el otro caso, en el que $k=2^p$ , elija $\sigma(k)=(p-1,p-1)$ .

Answer 2

Si sólo quieres definir tus funciones, y estás escribiendo para un público de lectores humanos, te recomendaría encarecidamente que escribieras de forma sencilla:

Definir las funciones $f$ y $g$ tal que para todo $a\le b$ sostiene que $$f(2^a+2^b)=a \qquad g(2^a+2^b)=b $$ y para cualquier número $n$ es decir no de la forma $2^a+2^b$ tenemos $f(n)=g(n)=0$ .

Estas condiciones obviamente definen $f$ y $g$ de forma única.

Esto es mucho más fácil de entender, y dará al lector una intuición mucho más clara sobre lo que estás haciendo, que tratar de evitar el uso de palabras en inglés. (Intentar deliberadamente evitar las palabras inglesas en la definición casi conduce a una mala exposición matemática).

Si está escribiendo no para un público humano, entonces lo que debe escribir depende fundamentalmente de lo que entenderá el público no humano.

En particular, si está tratando de programar un ordenador para poner en práctica las $f$ y $g$ para ti, no deberías buscar expresiones algebraicas en absoluto. Más bien, explotar el hecho de que hay operaciones que funcionan para este incorporada a las CPUs modernas . En los procesadores x86/x64 están implementados por el BSF y BSR instrucciones. Algunos lenguajes de programación las exponen de forma bastante directa, como por ejemplo Long.numberOfLeadingZeros(n) y Long.numberOfTrailingZeros(n) en Java -- sólo necesitas un poco de aritmética trivial para convertir el resultado de la primera de ellas a la representación que quieras.

Answer 3

Tenemos que relajar un poco su requisito debido al comentario de TheSilverDoe. Así que requerimos que para todos los $\boldsymbol{m \ge n \ge 0}$ , $\sigma(2^m + 2^n) = (m, n)$ . Entonces esto es posible. Primero defina $$ \tau(x) := \lceil \log_2(x) \rceil - 1, $$ por ejemplo, $\tau(2) = 0$ , $\tau(3) = \tau(4) = 1$ , $\tau(5) = 2$ etc. A continuación, defina $$ \sigma(x) := \Big(\tau(x), \tau \left( 1 + x - 2^{\tau(x)} \right) \Big). $$

Cómo funciona:

• $\tau(x)$ es el exponente en la mayor potencia de $2$ más pequeño que $x$ es decir, si $2^k < x \le 2^{k+1}$ entonces $\tau(x) = k$ .

• Para cualquier $m \ge n \ge 0$ sabemos que $2^m < 2^m + 2^n \le 2^{m+1}$ . Por lo tanto, $\tau(2^m + 2^n) = m$ .

• Así que para $x = 2^m + 2^n$ obtenemos $\tau(x) = m$ . Entonces, $1 + x - 2^{\tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$ y la mayor potencia de $2$ más pequeño que $2^m + 1$ es $2^m$ . Así, $$\tau(1 + x - 2^{\tau(x)}) = n,$$ así que $$ \sigma(x) = (m,n). $$

Observación: Parece probable que no haya manera de conseguir una función $\sigma$ que no utiliza funciones de suelo ni trucos similares. Una prueba de ello es que no hay ninguna función sobre los números reales que satisfaga $\sigma(2^x + 2^y) = (x,y)$ .