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
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
A simplification could be: Writing the digits in binary form and adding all the digits.
Binary form of 2018 = 10001111110
Sum of the digits = 7. Therefore f(2018)=7
f(0)=0
f(2n)=f(n)
f(2n+1)=f(n)+1
Hence, every odd number, the value of the function gets incremented by 1.
For ever even number, the value of the function remains unchanged.
Since the chain continues, the function works like binary tree.
f(2018)=f(2∗1009)=f(1009)
f(1009)=f(2∗504+1)=f(504)+1⟹f(2018)=f(1009)=f(504)+1
f(504)=f(2∗252)=f(252)⟹f(2018)=f(504)+1=f(252)+1
f(252)=f(2∗126)=f(126)⟹f(2018)=f(252)+1=f(126)+1
f(126)=f(2∗63)=f(63)⟹f(2018)=f(126)+1=f(63)+1
f(63)=f(2∗31+1)=f(31)+1⟹f(2018)=f(63)+1=f(31)+2
f(31)=f(2∗15+1)=f(15)+1⟹f(2018)=f(31)+2=f(15)+3
f(15)=f(2∗7+1)=f(7)+1⟹f(2018)=f(15)+3=f(7)+4
f(7)=f(2∗3+1)=f(3)+1⟹f(2018)=f(7)+4=f(3)+5
f(3)=f(2∗1+1)=f(1)+1⟹f(2018)=f(3)+5=f(1)+6
f(1)=f(2∗0+1)=f(0)+1⟹f(2018)=f(1)+6=f(0)+7=0+7=7