Sum of the largest odd divisors of the first n numbers.

Question

Hi, I've been working on topcoder recently and I stumbled upon this question which I can't quite make understand. The question is to find F(n) = f(1)+f(2)+....+f(n) for a given "n" such that f(n) is the largest odd divisor for n. There are many trivial solutions for the answer; however, I found this solution very intriguing.

int compute(n) {
if(n==0) return 0;
long k = (n+1)/2;
return k*k + compute(n/2);
}

However, I don't quite understand how to obtain a recursive relation from a problem statement such as this. Could someone help out?

Answer 1

I cannot see how that algorithm could possible work for the problem you described. (I'm going to assume that "N" and "n" refer to the same variable).

Given n = 12.

The largest odd divisor is 3 (the others are 1, 2, 4, 6 & 12)

F(12) is therefor f(1) + f(2) + f(3) or 1 + 1 + 3 or 5.

Using this algorithm:

k = (12+1)/2 or 6

and we return 6 * 6 + f(6), or 36 + some number which is not going to be negative 31.

Answer 2

I believe they are trying to use the following facts:

• f(2k+1) = 2k+1, i.e. the largest odd divisor of an odd number is the number itself.
• f(2k) = f(k). i.e the largest odd divisor of an even number 2m is same as the largest odd divisor of the number m.
• Sum of first k odd numbers is equal to k^2.

Now split {1,2,..., 2m+1} as {1,3,5,7,...} and {2,4,6,...,2m} and try to apply the above facts.

Answer 3

if this were Java, I'd say:

 import java.util.*;
 int sum_largest_odd_factors (int n){
      ArrayList<Integer> array = new ArrayList();//poorly named, I know
      array.add(1);
      for(int j = 2; j <= n; j++){
           array.add(greatestOddFactor(j));
      }
      int sum = 0;
      for(int i = 0; i < array.size(); i++){
           sum += array.get(i); 
      }
      return sum;
 }
 int greatestOddFactor(int n){
      int greatestOdd = 1;
      for(int i = n-((n%2)+1); i >= 1; i-=2){
          //i: starts at n if odd or n-1 if even 
          if(n%i == 0){
               greatestOdd = i;
               break;
               //stop when reach first odd factor b/c it's the largest
          }
      }
      return greatestOdd;
 }

This is admittedly tedious and probably an O(n^2) operation, but will work every time. I'll leave it to you to translate to C++ as Java and J are the only languages I can work with (and even that on a low level). I'm curious as to what ingenious algorithms other people can come up with to make this much quicker.