Is there an explicit function mapping $2^n+2^m$ to $(n,m)$?

Question

We know that the number $2^n+2^m$ is unique for $n,m\in\mathbb{N}$. Is there any explicit way of writing a function $\sigma:\mathbb{N}\to\mathbb{N}^2$ such that $$ \sigma(2^n+2^m)=(n,m), $$ for all $n,m\in\mathbb{N}$?

Remark (edit): Here, $(n,m)$ is to be interpreted as the unordered pair $\{n,m\}$, since I'm only interested in the pair. More specifically, I want to find functions $\sigma,f$ and $g$ such that $$ \sigma(k)=(g(k),f(k)), $$ where $k=2^{g(k)}+2^{f(k)}$, $\forall k \in\mathbb{N}$.

Answer 1

What do you think of $$\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)$$

This is well defined except when $k$ is a power of $2$.

In the other case where $k=2^p$, choose $\sigma(k)=(p-1,p-1)$.

Answer 2

We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $\boldsymbol{m \ge n \ge 0}$, $\sigma(2^m + 2^n) = (m, n)$. Then this is possible. First define $$ \tau(x) := \lceil \log_2(x) \rceil - 1, $$ for example, $\tau(2) = 0$, $\tau(3) = \tau(4) = 1$, $\tau(5) = 2$, etc. Then, define $$ \sigma(x) := \Big(\tau(x), \tau \left( 1 + x - 2^{\tau(x)} \right) \Big). $$

How it works:

• $\tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x \le 2^{k+1}$, then $\tau(x) = k$.

• For any $m \ge n \ge 0$, we know that $2^m < 2^m + 2^n \le 2^{m+1}$. Therefore, $\tau(2^m + 2^n) = m$.

• So for $x = 2^m + 2^n$, we get $\tau(x) = m$. Then, $1 + x - 2^{\tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus, $$\tau(1 + x - 2^{\tau(x)}) = n,$$ so $$ \sigma(x) = (m,n). $$

Remark: It seems likely that there will be no way to get a function $\sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $\sigma(2^x + 2^y) = (x,y)$.

Answer 3

If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:

Define the functions $f$ and $g$ such that for all $a\le b$ it holds that $$f(2^a+2^b)=a \qquad g(2^a+2^b)=b $$ and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.

These conditions obviously define $f$ and $g$ uniquely.

This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).

If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.

In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF and BSR instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n) and Long.numberOfTrailingZeros(n) in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.