Suma de los mayores divisores impares de los primeros n números

Question

He estado trabajando recientemente en topcoder y me encontré con esta pregunta que no puedo entender. La pregunta es encontrar F (n) = f (1) + f (2) + .... + f (n) para una "n" dada tal que f (n) es el mayor divisor impar para n. Hay muchas soluciones triviales para la respuesta; sin embargo, encontré esta solución muy intrigante.

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

Sin embargo, no entiendo muy bien cómo obtener una relación recursiva de un enunciado de problema como este. ¿Alguien podría ayudarme?

Answer 1

Creo que están tratando de utilizar los siguientes hechos:

• f (2k + 1) = 2k + 1, es decir, el mayor divisor impar de un número impar es el número sí mismo.
• f (2k) = f (k). es decir, el divisor impar más grande de un número par 2m es igual al divisor impar más grande del número m.
• La suma de los primeros k números impares es igual a k^2.

Ahora divide {1,2, ..., 2m + 1} como {1,3,5,7, ...} y {2,4,6, ..., 2m} y trata de aplicar los hechos anteriores.

Answer 2

No veo cómo podría funcionar ese algoritmo para el problema que describió. (Voy a suponer que "N" y "n" se refieren a la misma variable).

Dada n = 12.

El mayor divisor impar es 3 (los otros son 1, 2, 4, 6 & 12)

F (12) es para el mismo f (1) + f (2) + f (3) o 1 + 1 + 3 o 5.

el uso de este algoritmo:

k = (12 + 1)/2 o 6

y volvemos 6 * 6 + f (6), o 36 + algún número que no está funcionando g sea negativo 31.

Answer 3

si esto fuera de Java, diría:

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; 
} 

Esto es ciertamente tedioso y probablemente un O (n^2) la operación, pero trabajará en todo momento. Dejaré que te traduzca a C++ ya que Java y J son los únicos idiomas con los que puedo trabajar (e incluso eso en un nivel bajo). Tengo curiosidad sobre qué ingeniosos algoritmos pueden encontrar otras personas para hacer esto mucho más rápido.

Answer 4

si u están buscando suma de todos los divisores impares hasta n ..

Suma de todos los divisores impares de los primeros n números

...

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

de suma de todos los divisores en un rango l a 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;;; 

GRACIAS !!

Answer 5

Puede utilizar enfoque dinámico también el uso de espacios auxiliares

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; 

Como cuando el número es impar, entonces el número en sí será el mayor divisor impar y una [i] almacenará su valor y cuando el número es incluso entonces a [número/2] se almacenará en a [i] porque para el número par, el mayor divisor impar de número/2 será el máximo divisor impar del número.

También se puede resolver utilizando tres casos cuando el número es impar y luego sume el número si el número es potencia de 2, luego agregue 1 más si el número es par, excepto la potencia de 2 divida por 2 hasta obtener impar y agregue impar para sumar