Somme des plus grands diviseurs impairs des premiers numéros de n

Question

que je travaille sur TopCoder récemment et je suis tombé sur cette question que je ne peux pas tout à fait faire comprendre. La question est de savoir F (n) = f (1) + f (2) + .... + f (n) pour une donnée "n" de telle sorte que f (n) est le plus grand diviseur impair de n. Il existe de nombreuses solutions triviales pour la réponse; Cependant, j'ai trouvé cette solution très intrigante.

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

Cependant, je ne comprends pas tout à fait la façon d'obtenir une relation récursive d'un énoncé de problème comme celui-ci. Quelqu'un pourrait-il aider?

Answer 1

Je pense qu'ils essaient d'utiliser les faits suivants:

• f (2k + 1) = 2k + 1, à savoir le plus grand diviseur impair d'un nombre impair est le nombre lui-même.
• f (2k) = f (k). c'est-à-dire que le plus grand diviseur impair d'un nombre pair 2m est le même que le plus grand diviseur impair du nombre m.
• somme des k premiers nombres impairs est égal à k^2.

maintenant divisé {1,2, ..., 2m + 1} {comme 1,3,5,7, ...} et {2,4,6, ..., 2m} et essayez d'appliquer les faits ci-dessus.

Answer 2

Je ne peux pas voir comment cet algorithme pourrait travailler possible pour le problème que vous avez décrit. (Je vais supposer que "N" et "n" se réfèrent à la même variable).

Étant donné n = 12.

Le plus grand diviseur impair est trois (les autres sont 1, 2, 4, 6 & 12)

F (12) est à cet effet f (1) + f (2) + f (3) ou 1 + 1 + 3 ou 5.

utilisant cet algorithme:

k = (12 + 1)/2 ou 6

et nous reviendrons 6 * 6 + f (6), ou 36 + un certain nombre qui ne va pas g négatif 31.

Answer 3

si cela Java, je dirais:

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

C'est certes fastidieux et probablement un O (n^2) le fonctionnement, mais fonctionnera chaque fois. Je vais laisser à vous de traduire en C++ comme Java et J sont les seules langues que je peux travailler avec (et même que sur un faible niveau). Je suis curieux de savoir quels sont les algorithmes ingénieux que d'autres personnes peuvent utiliser pour accélérer le processus.

Answer 4

SI u recherchent somme de tous les diviseurs impairs jusqu'au n ..

Somme des diviseurs impairs des premiers numéros de n

...

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

pour somme de tous les diviseurs dans une plage l à 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;;; 

MERCI !!

Answer 5

Vous pouvez utiliser l'approche dynamique en utilisant également des espaces auxiliaires

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; 

Comme lorsque le nombre est impair, alors le nombre lui-même sera le plus grand diviseur impair et un [i] va stocker sa valeur et lorsque le nombre est même alors le a [nombre/2] sera stocké dans un [i] parce que pour le nombre pair le plus grand diviseur impair du nombre/2 sera le plus grand diviseur impair du nombre.

Il peut également être résolu en utilisant trois cas où le nombre est impair puis ajouter le numéro lui même si le nombre est de 2 puis ajouter 1 si le nombre est pair sauf la puissance de 2 diviser par 2 jusqu'à obtenir impair et ajouter étrange de somme.