4
$\begingroup$

Suppose we have this equation:

$y = 1 + x + \lceil \log_2(x)\rceil$

where $x$ is an integer > $0$.

How can we get $x$ as a function of $y$ (basically isolate $x$)? I don't understand how to handle the ceiling and the logarithmic function.

Thanks.

$\endgroup$
2
  • 3
    $\begingroup$ I think you want to get $x$ as a function of $y$. You already have $y$ as a function of $x$. $\endgroup$
    – joriki
    Mar 7 '13 at 1:42
  • $\begingroup$ yes you are right, I fixed it above. $\endgroup$
    – omega
    Mar 7 '13 at 1:50
3
$\begingroup$

There are two problems in getting $x$ as a function of $y$ ($y$ already is a function of $x$):

  1. The ceiling function ($\lceil x \rceil$) makes the function of $x$ discontinuous at the integers.

  2. Even if the ceiling function were not there, and the function was $y = 1 + x + \log_2(x)$, this could not be explicitly inverted. If we write it in the form $y = \log_2(2x 2^x)$, we that the Lambert W function is involved.

These two problems make the inversion difficult.

The poster did say what the domains of $x$ and $y$ were. The two obvious choices are the integers and the reals. In either case, an algorithm could be developed to get $x$, but it would have to be iterative and take into account the two problems stated above.

$\endgroup$
1
  • $\begingroup$ x is an integer > 0. $\endgroup$
    – omega
    Mar 7 '13 at 1:59
2
$\begingroup$

The fact that $x$ is a positive integer does not make it easier. I'll treat the general case where the natural domain is $(0,+\infty)$.

This function is piecewise affine.

For each integer $n$ and for $2^n<x\leq 2^{n+1}$, we have $n<\log_2x\leq n+1$ so $\lceil\log_2x\rceil=n+1$. Hence: $$ f(x)=x+1+n+1=x+n+2. $$

Now observe that
$$ \lim_{x\rightarrow 2^n-}f(x)=2^{n-1}+1+n<2^n+1+n+1=\lim_{x\rightarrow 2^n+}f(x). $$ It follows that the intervals $f((2^n,2^{n+1}])$ are pairwise disjoint.

So $f$ is a bijection $$ f:(0,+\infty)=\bigcup_{n\in\mathbb{Z}}(2^n,2^{n+1}]\longrightarrow \bigcup_{n\in\mathbb{Z}}f((2^n,2^{n+1}])=\bigcup_{n\in\mathbb{Z}}(2^n+n+2,2^{n+1}+n+2]. $$ We will find its inverse on each interval on each interval of the range.

So let $y\in (2^n+n+2,2^{n+1}+n+2]$. We are looking for $x\in(2^n,2^{n+1}]$ such that $$ f(x)=y\quad\Leftrightarrow\quad x+n+2 \quad\Leftrightarrow\quad x=y-n-2. $$ So $$ f^{-1}(y)=y-n-2\qquad\forall y\in (2^n+n+2,2^{n+1}+n+2]. $$ Unlike $f(x)$, I don't see how to express this $n$ in terms of $\log_2y$ with well-known functions. Given the gaps in the domain of $f^{-1}$, I doubt there is such a general formula.

$\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.