Representing integer as product of $2^n$ and an odd number

Question

I have a non-zero integer $x \in \mathbb{N}$, and I want to represent it as

$$ x = 2^N \cdot Q $$

where $N,Q \in \mathbb{N_0}$, and Q is an odd number. That means, $x$ is separated into an part that is a power-of-2, and an odd part.

Question: What is an explicit formular, using elementary operations, for $N(x)$ and $Q(x)$?

---

Special cases:

The two trivial special cases:

• If $x$ is odd: $N(x)=0$, $Q(x)=x$
• If $x$ is a power-of-two: $N(x)=\log_2(x)$, $Q(x)=1$

---

Added later: Elementary function:

I would like to get functions in the spirit of the $max$-function in terms summation, multiplication, and absolute, or as a limit, or any other elementary operations.

The solution by gammatester, while clearly answering the question about representation, uses conditions which i consider as not elementary. Is it possible to represent it in an simpler, more elementary way?

Answer 1

If $x=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the prime factorization of $x$, one can represent $\alpha_i(x)$ as

$$\alpha_i(x)=\lfloor \cos^2(x \pi/p_i) \rfloor + \lfloor \cos^2(x\pi/p_i^2) \rfloor +\cdots + \lfloor \cos^2(x \pi/p_i^x) \rfloor.$$

So in particular

$$N(x)=\lfloor \cos^2(x \pi/2) \rfloor + \lfloor \cos^2(x\pi/4) \rfloor +\cdots + \lfloor \cos^2(x \pi/2^x) \rfloor,$$ and then $Q(x)=x/2^{N(x)}$.

Update: a more elementary function. Let $N_K(x)$ be defined by $$N_k(x)=\left \lfloor \frac{x}{2^k} \right \rfloor - \left \lfloor \frac{x-1}{2^k} \right \rfloor.$$ Then $N_k(x)=1$ if and only if the positive integer $x$ is divisibly by $2^k$. To see this, let $x=2^ky+r$, where $0\leq r<2^k$. If $r\neq 0$, then $\lfloor x/2^k \rfloor =y$ and $\lfloor (x-1)/2^k \rfloor =y$, and so $N_k(x)=0$. While if $r=0$, then $\lfloor (x-1)/2^k \rfloor =y-1$, and so $N_k(x)=1$ in this case.

It follows that $$N(x)=\sum_{k=2}^\infty N_k(x)=\sum_{k=2}^x \left \lfloor \frac{x}{2^k} \right \rfloor - \left \lfloor \frac{x-1}{2^k} \right \rfloor,$$ since the largest possible value for $k$ such that $2^k$ divides $x$ cannot exceed $x$ ($2^x \geq x$ for all integers).

Answer 2

This is kind of an explicit formula for $x\ne 0$:

$$N(x) = \mathrm{max}\{n \in \mathbb{N} : 2^n \mid x\} \quad \text{and} \quad Q(x)=x / N(x).$$ Algorithmically you repeatedly divide $x$ by $2$ and count the number $N(x)$ of divisions until you get a non-zero remainder $Q(x).$

Answer 3

I think this is possible.

In fact I think it's possible to do this for every single function $f : \mathbb N \to \mathbb R$.

First, write $f$ as a limit of a sequence of piecewise linear functions $$f = \lim_{n \to \infty} F_n $$ where for each $i=2,..,n$ the restriction of $F_n$ to $[i-1,i]$ is the unique linear function with $F_n(i-1)=f(i-1)$ and $F_n(i)=f(i)$, the restriction of $F_n$ to $[-\infty,1]$ is constant, and the restriction of $F_n$ to $[n,\infty]$ is constant.

Next, every piecewise linear function $F(x)$ can be written as a finite formula involving only first degree functions $ax+b$ and max.