### From_ITK18_With_Love's blog

By From_ITK18_With_Love, history, 4 weeks ago,

Today, I get a problem.

Sum of greatest odd divisor of numbers in range $[a, b]$ with $a, b <= 10^9$

I found solution here : https://www.geeksforgeeks.org/sum-of-greatest-odd-divisor-of-numbers-in-given-range/

But I think the solution is not clear for the even number case.

Can find a better solution or more detailed explanation ?

 » 4 weeks ago, # | ← Rev. 3 →   +13 Your question is, what is the biggest odd divisor for a given number $n$? Let's call this function $f(n)$.For any Odd number: It is the number itself. Thus, $f(2n+1) = 2n+1$.For any Even number, it will be of the form $2n$. But the biggest odd divisor of $2n$ is the same as the biggest odd divisor for $n$. Thus $f(2n) = f(n)$.Now, let's say you need to find the sum of $f(n)$ up to 6.$= f(1) + f(2) + f(3) + f(4) + f(5) + f(6)$$= 1 + f(2) + 3 + f(4) + 5 + f(6)$$= 1+3+5 + f(1) + f(2) + f(3)$$= 9 +$ Sum of $f(n)$ upto $\frac{6}{2} = 3$.Which you can calculate recursively.