Functions together

[Avik Roy]

Define three functions $f,h:\mathbb {N} \cup \{0\} \times \mathbb {N} \to \mathbb {N} \cup \{0\}$ and $g:\mathbb {N} \times \mathbb {N} \to \mathbb {N} \cup \{0\}$ as such-
for $m<n$ \[f(m,n) =0 \] otherwise \[f(m,n) = g(m,n) + f \left (m - 2^{h(m,n)}n, n \right ) \] for $m \geq 2n $ \[g(m,n) = 2g \left (\left \lfloor {\frac {m} {2}} \right \rfloor, n \right ) \] \[h(m,n) = 1+ h \left (\left \lfloor {\frac {m} {2}} \right \rfloor, n \right ) \] otherwise \[g(m,n) = 1 \] \[h(m,n) = 0 \]
Find the function $f(m,n)$

[Corei13]

There's a problem in definition.
If, $m=n$, from the definition, we have, $f(m,m) = g(m,m) + f(0,m)$.
but $(0,m)$ not belongs to the domain of $f$.

[Avik Roy]

Edited the problem

[Corei13]

There's still problem, it's easy to show that, $h(m,n) = \lfloor log_2 m\rfloor$,
So, $n > 1$ implies, $m < 2^{h(m,n)}n$

[Avik Roy]

DJ, I think you got it wrong. I get $h(m,n) = \left \lfloor log_{2} \left ( \frac {m} {n} \right ) \right \rfloor $

[Corei13]

What about $\frac{m}{n} = 2^k$ ?

[Avik Roy]

I get it, it still get inputs form non-domains.
Editing once more, this should fix it for once and all

[Corei13]

Here's the sketch of the solution:

Prove by induction on $m$ that, $h(m,n) = \left \lfloor log_{2} \left ( \frac {m} {n} \right ) \right \rfloor$ for $m \geq n$ and that, $g(m,n) = 2^{\left \lfloor log_{2} \left ( \frac {m} {n} \right ) \right \rfloor}$ for $m \geq n$.

Then, if, $m > n$, then, $m = an + b, a,b \in \mathbb{N}\cup \{0\}, a > 0, b < n $
let $a = \sum_{i=0}^{r} a_i 2^i$ be the binary representation of $a$.
Then, $f(m,n) = a_r 2^{r} +f( \left ( \sum_{i=0}^{r-1} a_i 2^i \right ) n + b, n)$
$= \sum_{i=0}^{r} a_i 2^i + f(b,n) = \sum_{i=0}^{r} a_i 2^i = a = \left \lfloor \frac {m} {n} \right \rfloor $

[*Mahi*]

Nice and simple problem...especially the induction on $m$ in $g,h$ .

[Avik Roy]

The problem is inspired from the algorithm of performing division by using the rotation operation. I had written a note in facebook describing that process.