The function \(f\), defined for whole positive numbers, satisfies \(f(1)=1\) and also the rules \[f(2n)=2f(n),\] \[f(2n+1)=4f(n),\] for all values of \(n\). How many numbers \(n\) satisfy \(f(n)=16\)?
\(3\),
\(4\),
\(5\),
\(6\).
To begin with, we could calculate the first few terms: \(f(1)=1\), \(f(2)=2\), \(f(3)=2\), \(f(4)=4\). Is there a pattern? Not an obvious one.
It’s a help to ask how 16 factorises. We can do this using only the factors of \(2\) and \(4\) in \(5\) different ways, where the order matters, namely
- \(2\times 2\times 2\times 2\),
- \(4\times 2\times 2\),
- \(2\times 4\times 2\),
- \(2\times 2\times 4\) and
- \(4\times 4\).
To which values of \(n\) do these correspond?
corresponds to applying the first rule, namely \(f(2n)=2f(n)\), four times, giving \(n=2\times 2\times 2\times 2\times 1=16\) (the sequence of \(n\) values is \(1-2-4-8-16\)).
corresponds to applying the second rule once, followed by the first one twice, giving \(n=2(2\times2\times1)+1=9\) (the sequence is \(1-2-4-9\)).
corresponds to applying the first rule, the second rule, and then the first one again, giving \(n=2[2(2\times1)+1)]=10\) (the sequence is \(1-2-5-10\)).
corresponds to applying the first one twice, followed by the second one once, giving \(n=2\times2\times[2(1)+1]=12\) (the sequence is \(1-3-6-12\)).
corresponds to applying the second rule twice, giving \(n=2[2(1)+1]+1=7\) (the sequence is \(1-3-7\)).
Therefore we can have \(f(n)=16\) for \(5\) different values of \(n\), and the answer is (c).
Alternatively, we can find \(f(n)\) for \(n = 1\) to \(16\), and notice that \(f(n) \geq 16\) for \(n = 8\) to \(16\).
This means that \(f(n) > 16\) for \(n = 17\) to \(32\), since applying the first rule to one of these numbers \(n\) gives \(f(n)\) to be at least \(32\), and applying the second rule gives \(f(n)\) to be at least \(64\).
We can extend this argument naturally to show \(f(n) > 16\) for all \(n > 16\), and so there are just five values of \(n\) where \(f(n) = 16\). The answer is (c).
