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?

  • $\begingroup$ 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 $\endgroup$ – Aaron Zolotor Oct 28 '18 at 14:02
  • 2
    $\begingroup$ What do you mean with find? An explicit formula? For $x\ne 0$ your $N(x)$ is the valuation $\nu_2(x)$ $\endgroup$ – gammatester Oct 28 '18 at 14:04
  • $\begingroup$ Thank you, i clarified. Gammatester, the connection to valuation is very interesting. I think you can convert your comment into an answer, right? $\endgroup$ – NicoDean Oct 28 '18 at 14:20
  • $\begingroup$ @LeeMosher please try again, i initially had a wrong link, but fixed it. $\endgroup$ – NicoDean Oct 28 '18 at 14:55
  • 3
    $\begingroup$ 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.$ $\endgroup$ – 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).

  • $\begingroup$ 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. $\endgroup$ – NicoDean Oct 28 '18 at 17:54
  • $\begingroup$ @NicoDean thanks I added a more elementary function. Please feel free to edit my post by adding how you can express the floor function. $\endgroup$ – 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).$

  • $\begingroup$ 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! $\endgroup$ – NicoDean Oct 28 '18 at 14:47
  • $\begingroup$ 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$. $\endgroup$ – 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.


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.