1
$\begingroup$

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?

$\endgroup$
1
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ What is wrong with the bijection in the link above? $\endgroup$ – user7530 Sep 13 '13 at 13:58
  • $\begingroup$ @user7530 Edited to reflect what I wanted to say $\endgroup$ – AlexR Sep 13 '13 at 14:02
  • $\begingroup$ +1 Ok. Whether or not there exists a formula for $n$ and $m$ is an interesting question, now.., $\endgroup$ – user7530 Sep 13 '13 at 14:35
  • $\begingroup$ @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. $\endgroup$ – AlexR Sep 13 '13 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.