Capta1n_Shy's blog

By Capta1n_Shy, history, 3 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.