# How to find a formula for this bijection?

We know that there is a bijection of the set $S:= \{ 2^m 3^n \mid m, n \in\mathbb Z, m,n\geq 0\}$ onto the set $\mathbb N$ of natural numbers. How to find a simple formula for such a map?

Here's one: $$2^m 3^n \mapsto 2^m (2n+1).$$

Here, I'm assuming $\mathbb{N}=\{1,2,\ldots\}$, otherwise we subtract $1$ from the formula.

We can prove both injectivity and surjectivity via the Fundamental Theorem of Arithmetic.

There is no simple formula, because an enumeration is obtained by diagonalisation:

$$2^n3^m \mapsto \phi(n,m)$$ Where $\phi: \mathbb N^2 \to \mathbb N$ is the diagonal enumeration.
You will not find a "simple" formula for $\phi^{-1}$ and I am not aware of any simple formula which maps $2^n3^m \mapsto (n,m)$ either...

Assuming we know (or have an "oracle" for) $p_2, p_3:S\to\mathbb N$ to give the respective powers of $2, 3$ in the prime factor decomposition incremented by $1$, we can get $$\pi:S\to\mathbb N,\qquad x \mapsto \frac{1}{2}(p_2(x) + p_3(x))(p_2(x) + p_3(x) + 1) + p_3(x)$$ (according to this)

• What is wrong with the bijection in the link above? – user7530 Sep 13 '13 at 13:58
• @user7530 Edited to reflect what I wanted to say – AlexR Sep 13 '13 at 14:02
• +1 Ok. Whether or not there exists a formula for $n$ and $m$ is an interesting question, now.., – user7530 Sep 13 '13 at 14:35
• @user7530 As far as I know this would be somewhat an oracle for PFD, which is not known today. However, iterative algorithms will be able to proceed much quicker. Suggestion:  1. Convert $x$ to binary and count the trailing zeros $n$ ($n+1=p_2(x)$)  2. Convert $x >> n$ to ternary and count the trailing zeros $m$ again ($m+1 = p_3(x)$)  Base conversion is not too fast and no closed formula though. – AlexR Sep 13 '13 at 14:38