### From_ITK18_With_Love's blog

By From_ITK18_With_Love, history, 5 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 ?

Sorry, my english was bad.

Thanks you.

• 0

 » 5 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.
 » 5 weeks ago, # |   +1 Let answer for range [1, N] be f(N). You can find answer for range [L, R] as f(R) — f(L — 1). Now let's solve for range [1, N]. Each number i in this range will have some power of 2 as it's factor. Let's analyse highest power of 2 in each number.I will explain this using N = 20 for example. Number's with 2^0 as factor: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Number's with 2^1 as factor: 2, 6, 10, 14, 18. Number's with 2^2 as factor: 4, 12, 20. Number's with 2^3 as factor: 8. Number's with 2^4 as factor: 16. Number's with 5 and higher power of 2 does not exist in this range.Now if you extract those higest powers, you'll just get some oodd numbers, which will be the greatest odd divisor of each number. For 2^0: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. For 2^1: 1, 3, 5, 7, 9. For 2^2: 1, 3, 5. For 2^3: 1. For 2^4: 1.So basically, we will have some odd numbers from range [1, X]. What will be this X? That will depend on power of 2. Let highest power of 2 be i, then we will just be using odd numbers in the range [1, N / (2^i)].Finally, the solution is: Iterate over all powers i of 2, sum up to odd numebers in the range [1, N / (2^i)]. Some small details: If you're considering the range [1, X], there will the (X + 1) / 2 odd numbers in the range. Also, sum of first K odd numbers is K * K. Here's my implementation.