Question

Let N N denote the natural numbers {1,2,3,4,...}. Observe a f that satisfies f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1 for all n that are natural numbers. Write a algorithm for f(n).

Answer 1

f(1)=1
f(2)=1
f(3)=2
f(4)=2
f(5)=3
f(6)=3
So f(n) will be ⌈n/2⌉