help deriving a closed formula for this "magic function"

Question

I'm having trouble coming up with a closed formula for $n$ from the sequence of numbers generated by this function:

The following mystery function $M : N \times N \rightarrow N $ is defined by: $$ M(m,n) = \begin{cases} m & n < 2m +1 \\ M(m+1, n-2m-1) &n \ge 2m + 1 \end{cases} $$

If that looks confusing here's an algorithm representing the logic:

int M(int m, int n)
{
    if (n < 2*m + 1)
        return m;
    else
        M(m + 1, n - 2*m - 1);
}

Here's what I have to do:

1. Evaluate $M(0,n)$ for $n \in \{0,...,10\}$.

   1. $n = 0$ : $M(0,0) = 0$
   2. $n = 1$ : $M(0,1) = 2$
   3. ...
   4. I evaluated each $n$ from $0$ to $10$ on paper, and the sequence I got is: $0,1,1,1,2,2,2,2,2,3,3$ I verified this output by running my algorithm in C.

2. Provide a closed formula for $M(0,n)$

   1. This is where I'm lost. I know what a closed formula is. It's a formula to find the value of $M(0,n)$ with $n$ in the formula... I ran my program again, but this time from n = 0 to 100, and see a pattern of 0, three 1's, five 2's, seven 3's, nine 4's... and so on... But I don't see how to tie this to n. I think I've been up too late. Any help/insight is appreciated!

Answer 1

Take a look at what happens when you apply this procedure to $M(0,n)$. Then see whether you can identify a pattern.

To simplify things, let's first assume that $n$ is large enough so that we are always in the case that $n \geq m$. That gives us the following: $$ M(0,n)=M(1,n-1)=M(2,n-4)=M(3,n-9)=M(4,n-16)=M(5,n-25) $$ Do these numbers $1,4,9,16,25,\dots$ satisfy a pattern?

Looking at the above, for which values of $n$ do we get the answers $0,1,2,3,4,\dots$? For example, we stop at the stage $M(3,n-9)$ if

• We did not stop at the previous stage, so $n-4 \geq 2(2)+1=5$ or $n \geq 9$
• We do stop at this stage, so $n-9< 2(3)+1=7$ or $n<16$.

So we stop at this stage if $9 \leq n < 16$, and in this case we output $3$.

This approach yields the following: $$ \begin{array}{c|c} M(0,n) & n \\ \hline 0 & 0\leq n <1 \\ 1 & 1 \leq n <4 \\ 2 & 4 \leq n <9\\ 3 & 9 \leq n< 16\\ 4 & 16 \leq n<25\\ \end{array} $$ Do you see a way to express this a function of $n$?

(Why do the numbers $1,4,9,16,25, \dots$ appear? Take a look at this question here.)