A simple expression to map $\mathbb N^*$ bijectively to $\mathbb N$

Question

Let $\mathbb N = \{ 1,2,3,\ldots \}$, then by the well-known "Cantor"-Scheme we have $\mathbb N \times \mathbb N \cong \mathbb N$. But even nicer is that we can write this scheme $\varphi : \mathbb N \times \mathbb N \to \mathbb N$ as a simple function¹ (quadratic polynomial) $$ \varphi(n,m) = n + \sum_{i=1}^{n+m-2} i = \frac{1}{2}(n+m-1)(n+m-2) + n. $$ which could be seen by looking at the infinite grid $\mathbb N \times \mathbb N$ the right way quite simply². Setting $$ (n,m,k) \mapsto \varphi(\varphi(n,m), k) $$ and so on we see that $\mathbb N^k \cong \mathbb N$ and we still got a simple formula. But now consider $$ \mathbb N^* := \bigcup_{k=1}^{\infty} \mathbb N^k $$ which as a countable union of countable sets must themselve be countable. But beside this abstract proof, does there exists some simple (maybe polynomial) function which realises this bijection?

Denote by $p_n$ the $n$-th prime number and define $\psi$ by $\psi(n_1, \ldots, n_k) := 2^{n_1} 3^{n_2} \cdots p_k^{n_k}$, this gives such a correspondence based on the unique prime factorisation, but maybe you know some simpler ones, that could also be evaluated fast on a computer (computing the $n$ prime is not computationally simple).

---

Footnotes:

1. For $\varphi : \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0$ we have $$ \varphi(n,m) = n + \sum_{i=1}^{n+m} i = n + \frac{1}{2}(n+m)(n+m+1). $$

2. For $(n,m)$ consider the diagonal where $i + j = m + n$ and sum everything underneath this diagonal, this is exactly $\sum_{i=1}^{n+m}$, after this add $n$ to move on this diagonal to the right point.

Answer 1

The following map $f:\mathbb{N}^* \to \mathbb{N}$ should be a bijection. If $u$ is the empty word, let $f(u) = 0$ and if $u = (n_0, n_1, \dotsm, n_k) \in \mathbb{N}$, let $$ f(u) = 10^{n_0}10^{n_1} \dotsm 10^{n_k} $$ where the right hand side is the binary representation of an integer.

Answer 2

Here is an idea which should work.

Let $n >0$ be a positive integer.

Define $k_0=n$, and recursively, as long as $k_j \neq 0$ define $$ k_{j} =2^{k_{j+1}} m_{j+1} \, \mbox { with } m_{j+1} \mbox{ odd } $$

This process ends after $t$ steps, when $k_t=0$, or equivalently $k_{t-1}$ is odd.

Now define $$f(n) =( \frac{m_1-1}{2}, \frac{m_2-1}{2},.., \frac{m_t-1}{2} ) \in \mathbb N^t$$

I think it is easy to show that this is a bijection as you want. Note that $f$ maps the odd numbers to $\mathbb N$, the numbers for which the power of two is odd to $\mathbb N^2$ and so on.

This is easy to compute, as all you need is to figure the power of two in an integer.