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, 2013 at 1:42
  • $\begingroup$ yes you are right, I fixed it above. $\endgroup$
    – omega
    Mar 7, 2013 at 1:50

2 Answers 2

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, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .