# help deriving a closed formula for this “magic function”

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!
-

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

-
I really do appreciate the time you put into writing this answer, but I still don't see it. I see that the 1,4,9,... pattern is consecutive squares starting at n=1 – user87509 Jul 25 '13 at 11:37
The function is the floor of the square root function, the largest whole number less than $\sqrt n$. So it will be 3 between $9=3^2$ and $15=4^2-1$, it will be 4 between $4^2$ and $5^2-1$. – Tom Cooney Jul 25 '13 at 11:41
I don't remember where I first saw it; it's more a convenient way of writing things than anything else. – Tom Cooney Jul 25 '13 at 11:49
The floor function is going to be the shortest way of writing down the answer. You could always write something like $M(0,n)=N$ for all $n$ such that $N^2 \leq n <(N+1)^2$, but that's just a longer way of writing the same thing. – Tom Cooney Jul 25 '13 at 11:56
Thanks! Well, so $M(0,n) = f(n) = \lfloor \sqrt(n)\rfloor$ is the way to write this? – user87509 Jul 25 '13 at 12:03