1. ## Weird function

Let $\displaystyle f$ be a function on the positive integers defined by
$\displaystyle f(n)=\begin{cases} \displaystyle\frac{n}{2}&\text{if }n\text{ is even}\\ n+1&\text{if }n\text{ is odd} \end{cases}$
Now let $\displaystyle g(n)$ be defined as the number of times $\displaystyle f$ must be applied to $\displaystyle n$ for it to first equal 1.
For example, $\displaystyle g(2)=1$ because $\displaystyle f(2)=1$ and $\displaystyle g(5)=5$ because $\displaystyle f(f(f(f(f(5)))))=1$.
How many solutions are there to the equation $\displaystyle g(n)=20$

2. I tried doing it reverse order, and came at a guess of 524288 or 38, don't suppose you have the answer do you? =)

3. Originally Posted by Nyoxis
I tried doing it reverse order, and came at a guess of 524288 or 38, don't suppose you have the answer do you? =)
The answer I got was 4181, but I need some confirmation.

4. Originally Posted by math sucks
The answer I got was 4181, but I need some confirmation.
I've been playing with this for a bit and found out the following.

We may derive an expression for g(x) by considering the decomposition of x into $\displaystyle x = 2^n + r$. In this way we may derive a recursively defined series that generates a value for any g(x) in terms of n and r. I have not carried out the full treatment, but have derived the following table:
$\displaystyle 2^n~\implies~n \text{ steps}$
$\displaystyle 2^n + 1 ~\implies~2n + 1 \text{ steps}$
$\displaystyle 2^n + 2 ~\implies~2n \text{ steps}$
$\displaystyle 2^n + 3 ~\implies~2n \text{ steps}$
$\displaystyle 2^n + 4 ~\implies~2n - 1 \text{ steps}$
$\displaystyle 2^n + 5 ~\implies~2n - 1 \text{ steps}$
$\displaystyle 2^n + 6 ~\implies~2n - 1 \text{ steps}$
$\displaystyle 2^n + 7 ~\implies~2n - 1 \text{ steps}$
$\displaystyle 2^n + 8 ~\implies~2n - 2 \text{ steps}$

I think you can guess how the pattern goes from this.

So to find g(5), for example, we do the following: $\displaystyle x = 5 = 2^2 + 1$. This is of the form $\displaystyle x = 2^n + 1$ where n = 2. So $\displaystyle g(5) = 2(2) + 1 = 5$. Thus g(5) = 5 as expected.

We wish to find x such that g(x) = 20. We have several possibilities just in the small table I derived above:
$\displaystyle 20 = n \implies n = 20 \implies x = 2^{20}$
$\displaystyle 20 = 2n \implies n = 10 \implies x = 2^{10} + 2 \text{ or } x = 2^{10} + 3$
$\displaystyle 20 = 2n - 2 \implies n = 11 \implies x = 2^{11} + 8$
etc.

So I've got g(1048576) = g(2056) = g(1027) = g(1026) as just some possibilities.

Once you derive the general relationship you should be able to just write x in terms of n and r.

(By the way, double check 4181; I'm getting g(4181) = 18.)

-Dan

5. By 4181, I meant that there are 4181 many solutions to the equation $\displaystyle g(n)=20$, not that $\displaystyle g(4181)=20$. The question does not require you to find the general form of the solutions, just how many there are.