The sum of the largest odd divisors of the first n numbers

Question

I recently worked on topcoder and I came across this question that I cannot understand. The question arises: find F (n) = f (1) + f (2) + .... + f (n) for a given "n" for which f (n) is the largest odd divisor for n. There are many trivial solutions to 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 do not quite understand how to get a recursive relation from a problem statement such as this. Can anyone help?

Answer 1

I believe that they are trying to use the following facts:

• f (2k + 1) = 2k + 1, that is, the largest odd divisor of an odd number is the number itself.
• f (2k) = f (k). those. the greatest odd divisor of an even number 2m is the same as the largest odd divisor of an number m.
• The sum of the first k odd numbers is k ^ 2.

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

Answer 2

You can use a dynamic approach using helper spaces

 int sum=0; int a[n+1]; for(int i=1;i<=n;i++){ if(i%2!=0) a[i] = i; else a[i] = a[i/2]; } for(int i=1;i<=n;i++){ sum+=a[i]; } cout<<sum; 

As and when the number is odd, the number itself will be the largest odd divisor, and [i] will keep its value, and when the number is even, then [number / 2] will be stored in [i], because for an even number the largest odd divisor of the number / 2 will be the largest odd divisor of a number.

It can also be resolved using three cases where the number is odd and then adds the else else number if the number is 2, then add 1 else if the number is equal, except for power 2, divide it by 2 until you get an odd value , and add this odd let down.

Answer 3

I do not see how this algorithm can 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 remaining 1, 2, 4, 6, and 12)

F (12) for this f (1) + f (2) + f (3) or 1 + 1 + 3 or 5.

Using this algorithm:

k = (12 + 1) / 2 or 6

and return 6 * 6 + f (6) or 36 + some number that will not be negative 31.

Answer 4

If it were Java, I would 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 the largest } } return greatestOdd; } 

This is admittedly tedious and possibly operation O (n ^ 2), but will work every time. I will leave it to you to translate to C ++, since Java and J are the only languages ​​I can work with (and even this is at a low level). I'm curious what ingenious algorithms other people can offer to do this much faster.

Answer 5

IF u look for the sum of all odd divisors up to n ..

The sum of all odd divisors of the first n numbers

...

 for(long long int i=1;i<=r;i=i+2) { sum1=sum1+i*(r/i); } 

for the sum of all divisors in the range from l to r

 for(long long int i=1;i<=r;i=i+2) { sum1=sum1+i*(r/i); } for(long long int i=1;i<l;i=i+2) { sum2=sum2+i*((l-1)/i); } ans=sum1-sum2;;; 

THANKS!!