Question 491615: f(1)=1,f(2n)=f(n),and f(2n+1)=f(2n)+1
Find max of f(n) when n is greater than or
equal to 1 and less than or equal to 1994.
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! Assuming f is only defined on {1,2,...,1994}, we have
 = f(2) = f(4) = ... = f(2048) = 1)
 = f(2n) + 1 = f(n) + 1) for all valid n. Hence,
 = f(1)+1)
 = f(2)+1)
 = f(3)+1)
.
.
.
There is a slick algorithm that can be used to find the maximum value of f(n). First, assume that n is odd (this is because f(2n) = f(n), so f(n*2^k) = f(n)). We can now "increment" by 1 because f(3) = f(1)+1 = 2, then we use a recursive definition to obtain f(7) = f(3)+1 = 3, and so on. We have
 = f(1)+1 = 2)
 = f(3) + 1 = 3)
 = f(7) + 1 = 4)
.
.
.
 = k)
The largest k we can allow is 11, because 2^12 is too large for our domain. Hence, the maximum value of f(n) is 11.
|
|
|
