lani1akea's blog

By lani1akea, history, 6 weeks ago, In English,

Hello! I have a question. Find the sum of greater odd divisors of 1 to n. n <= 10^9 . For example: n == 7 and f(n) = greater odd divisor of n f(1) = 1 , f(2) = 1 , f(3) = 3 , f(4) = 1 , f(5) = 5 , f(6) = 3 , f(7) = 7 and answer is 21

AND PLEASE TELL ME YOUR SOLUTION'S PROOF

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lani1akea (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you soo much !

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's completely different problem, isn't it? Let's denote sum[x] as the sum of greater odd divisors of all numbers from 1 to x and gr[x] as the greater odd divisor of number x. If x is odd then gr[x] = x, if x is even then gr[x] = gr[x/2]. So we can divide our sum[n] on two parts, i.e. even and odd parts:

    $$$sum[n] = \sum_{i=1}^{n} gr[i] = \sum_{i=1,odd}^{n} i + \sum_{i=2,even}^{n} gr[i] = $$$
    $$$(\frac{n+1}{2})^2 + sum[n/2]$$$

    We have simple recursion here.

    Code