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

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?

• Is $0$ contained in the naturals for you? Otherwise this doesn't work. No odd number can be expressed as a multiple of 2 since even*odd=even – Aaron Zolotor Oct 28 '18 at 14:02
• What do you mean with find? An explicit formula? For $x\ne 0$ your $N(x)$ is the valuation $\nu_2(x)$ – gammatester Oct 28 '18 at 14:04
• Thank you, i clarified. Gammatester, the connection to valuation is very interesting. I think you can convert your comment into an answer, right? – NicoDean Oct 28 '18 at 14:20
• @LeeMosher please try again, i initially had a wrong link, but fixed it. – NicoDean Oct 28 '18 at 14:55
• Does this count: $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.$ – Marco Oct 28 '18 at 15:06

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).

• Thank you. How about you add the specific formular for $N(x)$ from your comment, in order to fully answer my question. I will upvote and probably accept your answer (if nothing more elementary appears in near future, which i doubt). This method is really cool - thanks. – NicoDean Oct 28 '18 at 17:54
• @NicoDean thanks I added a more elementary function. Please feel free to edit my post by adding how you can express the floor function. – Marco Oct 29 '18 at 11:33

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

• Thank you. Your answer is clearly interesting. However, would it possible to write the representation in terms of more elementary functions? I updated the question to cover this. Thanks! – NicoDean Oct 28 '18 at 14:47
• I doubt that you can find such a function in your given sets. At least you additionally need a sort of $\mathrm{mod}$ function, and even then the function is wildly jumping, look and $x=16,17,18$. – gammatester Oct 28 '18 at 15:04

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.