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

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

Answer 2

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.