Question

A function f satisfies f(0) = 0, f(2n) = f(n), and f(2n + 1) = f(n) + 1 for all positive integers n. What is the value of f(2018)? 

Answer 1

It is recursive functions ,

f(2018)-->f(2*1009)

as per 2nd eq, f(2*1009) = f(1009)

f(2 * 504 + 1 ) = f(504) + 1

f(2 * 251) = f(251)

f(2 * 125 + 1) = f(125) + 1

f(2 * 62 + 1) = f(62) + 1

f(2 * 31) = f(31)

f(2 * 15 + 1) = f(15) + 1

f(2 * 7+ 1) = f(7) + 1

f(2 * 3+ 1) = f(3) + 1

f(2 * 1+ 1) = f(1) + 1

f(2 * 0+ 1) = f(0) + 1

as per given , f(0) = 0

count all 1's

therefore f(2018) = 8

Answer 2

Whenever such pattern comes try to resolve them into factors and then calculate the value of them from it,

Now,

f(0)=0

f(n) = f(2n)

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

So,

f(2018) = f(2 ×1009)

Now,

1009 is odd so,

f(1009) = f(504) + 1

Now,

504 is again even so,

f(504) = f(252)

f(252) = f( 126)

f(126) = f(63)

Now,

63 is odd so,

f(63) = f(31) +1

f(31) = f(15) +1

f(15) = f(7) +1

f(7) = f(3) +1

f(3) = f(1) +1

f(2) = f(1)

f(1) = f(0)+1

f(1)=1

So,

if you keep on adding the values till above you will get the answer as

f(2018) =7

Hope this helps !!!!!!!!!!!!!