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)
Answers
Given, f(0) = 0
f(2n) = f(n) .........(i)
and f(2n +1) = f(n) + 1 ... ....(ii)
now, f(2018) = f(2 × 1009) = f(1009) [from eq(i)]
f(1009) = f(2 × 504 + 1) = f(504) + 1 [ from eq(ii)]
f(504) + 1 = f(2×252) + 1 = f(252) + 1 [from eq(i)]
f(252) + 1 = f(2×126) + 1 = f(126) +1 [from eq(i)]
f(126) + 1 = f(2×63)+1 = f(63) + 1 [ From eq(i)]
f(63) + 1 ={ f(2×31 + 1)} + 1 ={ f(31) +1 } + 1 [ from eq(ii)]
f(31) + 2 = f(2 × 15 + 1) + 2 = f(15) + 3 [from eq(ii)]
f(15) + 3 = f(7) + 4 [from eq (ii)]
f(7) + 4 = f(3) + 5 [from eq(ii)]
f(3) + 5 = f(1) + 6 [ from eq(ii)]
f(1) + 6 = f(2 × 0 + 1) + 6 = f(0) + 1 + 6 [from eq(ii)]
f(0) + 7 = 0 + 7 = 7 [ as f(0) = 0 is given ]
hence, f(2018) = 7
First of all, one can write the digits by means of binary form.
Consider the binary form of 2018 is 10001111110.
Sum of the digit is equivalent to 7.
So f (2018) = 7.
For the odd number, the value of the function in increased by 1.
For even number, the function becomes unchanged.