The function f, defined for whole positive numbers, satisfies f(1) = 1 and also the following rules

f(2n) = 2f(n) and f(2n + 1) = 4f(n)

The question is, how many numbers n satisfy f(n) = 16?

Once again, this is a good moment to pause the article and give the problem a go yourself. When you’re ready, keep reading for the solution. And if you come up with your own approach, feel free to share it in the comments — I’d love to see how you tackled it.

Don’t forget to subscribe to our YouTube channel for more maths puzzles, it’s my goal to reach 100k subscribers someday. 

---

Solution

For any positive integer value of k, we can work out f(k) by considering whether k is even or odd, then using either the first rule or the second rule to work our way downwards until we reach 1, when we can apply the fact that f(1) = 1.

On the way down, we’ll gain factors of 2 and 4, and we would like the product of these to be 16.

Let’s write

and

They help us represent the expressions inside the brackets of the function.

So now we have the rules as

The challenge is to apply g and/or h several times (starting from the number 1), so that we make 16 = 2^4.

We gain a factor of 2 each time we apply g, and a factor of 2^2 each time we apply h.

So we could use g four times, or g twice and h once, or h twice. The order that we apply the functions matters, so that middle case gives us three values of n for which f(n) = 16.

Concretely, we have

Clearly there are 5 values of n that satisfy f(n) = 16.

Did you approach this problem differently? Let me know 🙂

And that’s our answer. How amazing. Hey, don’t forget to clap👏 the article as a token of appreciation. Thank you 🦁