5
$\begingroup$

Please help me with this exercise...

I already showed that the function is bijective, and I do not know how to find the inverse of the function...

Be the function $f : \mathbb{N} \times \mathbb{N}  \rightarrow \mathbb{N}$ defined by $f(m,n) = 2^m (2n+1) - 1$

$\endgroup$
3
$\begingroup$

Let $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ be given by $$(m,n)\mapsto 2^m(2n+1)-1.$$ We know that $f$ is bijective. Let's construct the inverse.


Given an integer $M$, by the fundamental theorem of arithmetic, $M+1$ can be written in a unique power of prime numbers, namely $$M+1=2^m\cdot \prod_{\substack{p_i\geq 3\\p_i\text{ prime}}}p_i^{s_i}=2^m q.$$ But, $q$ is an odd number, which means it can be written uniquely as $q=2n+1$. We thus have $M+1=2^m(2n+1)$ with $m,n$ unique by constuction. Define your inverse map to be $$M\mapsto (m,n)$$ as defined above. This answers your question.

$\endgroup$
2
$\begingroup$

Given $q\in \mathbb N $, we look for integers $m,n $ such that

$$2^m (2n+1)=q+1$$

we write $q+1$ as a product of powers of prime numbers as

$$q+1=2^a.3^b.5^c... $$ $=2^a\times$ an odd integer which has the form $2p+1$.

thus $m=a,n=p $.

For example, $q=59$.

then $$q+1=60=2^2.3.5=2^2 (2.7+1) $$

hence $$f (2,7)=2^2 (2.7+1)-1=59$$

$\endgroup$
2
$\begingroup$

The reason it's bijective is cause every number can be written as a unique product of a power of two and an odd number.

So the inverse function is the function that takes in a natural number and follows these instructions:

  1. Add one
  2. factor the result into a power of two times an odd number $2^mq$
  3. $m$ is the exponent of two in this factorization and $n = \frac{q-1}{2}$
  4. Return the ordered pair $(m,n)$.
$\endgroup$
0
$\begingroup$

The other answers do a good job explaining that if $p=f(m,n)$ then $2^m$ is the greatest power of two that divides $p+1$. However, so far all the inverse functions are described in words. If you want a formula for the inverse function, first define $\mathrm{Ruler}(q)$ to be the exponent of the highest power of two that divides $q$. This is a common function in number theory, although if you search for it you may find the same-named but different Thomae's function on the real numbers. Python code for $\mathrm{Ruler}()$ is given at the end of this answer though in theoretical mathematics it would be defined by recursion. Given that function, $m$ is easy to find as $\mathrm{Ruler}(p+1)$ and the hard part is showing a formula for $n$. Here are three expressions for your inverse function with the result given as an ordered pair $(m,n)$.

In MathJax:

$$f^{-1}(p)=\left(\mathrm{Ruler}(p+1),\ \frac{\dfrac{p+1}{2^{\mathrm{Ruler}(p+1)}}-1}2\right)$$

In an inline expression (using two asterisks for exponentiation rather than the caret since I can't figure out how to escape the caret character in MathJax):

$$f^{-1}(p)=(\mathrm{Ruler}(p+1), ((p+1)/2\mathrm{**}\mathrm{Ruler}(p+1)-1)/2)$$

As a Python code line:

(Ruler(p+1), ((p+1) // 2**Ruler(p+1) - 1) // 2)

And here is my Python code for the ruler function:

def ruler(n):
    """Return the exponent of the highest power of 2 dividing n.  This
    is also the number of trailing zeros in the binary expansion of n,
    or the number of trailing ones in the binary expansion of n - 1.
    A graph of this resembles the markings of fractions of an inch on a
    ruler. See sequence A007814 at oeis.org."""
    n = int(n)
    if not n:
        raise ValueError('ruler(0) is undefined')
    result = 0
    while not (n & 1):
        n >>= 1
        result += 1
    return result
$\endgroup$

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.