Exprimer la factorielle n comme la somme de nombres consécutifs

Nous aborderons deux méthodes pour découvrir comment exprimer la factorielle d'un nombre comme la somme de nombres consécutifs. La première méthode est la méthode directe et simple, tandis que dans l'autre méthode nous utilisons le concept de progression arithmétique pour la rendre moins complexe en termes de temps et d'espace occupé.

Énoncé du problème

Étant donné un nombre, nous devons trouver un moyen d'exprimer la factorielle du nombre comme la somme de nombres naturels consécutifs.

Cela implique deux fonctions différentes -

• Trouvez la factorielle d'un nombre.

• Trouvez le nombre de façons dont un nombre peut être exprimé comme la somme de nombres naturels consécutifs.

Exemple 1

Given : Number = 3
Result: 1

Nous savons tous que la factorielle de 3 est 6, qui peut s'écrire 1+2+3, donc notre réponse est : 1 voie.

Exemple 2

Given: Number = 4
Result: 1

Comme nous le savons tous, la factorielle de 4 est 24, ce qui peut s'écrire 7+8+9, donc notre réponse est : 1 voie.

Méthode 1

Il s'agit d'une méthode simple où nous trouvons d'abord la factorielle d'un nombre, puis calculons le nombre de façons dont il peut être exprimé comme la somme de nombres naturels consécutifs. La méthode consiste à exprimer la factorielle sous la forme d'une série de longueur arithmétique len+1 sous la forme -

Factorial of Number = p + (p+1) + (p+2) + … + (p+len) 
So, p = (Number- len*(len+1)/2)/(len+1) 
We will check for the values of len from 1 to len*(len+1)/2<Number

Lorsque nous obtenons len ​​sous forme d'entier positif, nous le considérons comme une solution.

Exemple

Dans l'exemple ci-dessous, nous essayons de trouver le nombre de façons d'exprimer la factorielle d'un nombre comme la somme de nombres consécutifs.

#include <bits/stdc++.h>
using namespace std;

// code for obtaining number of possible solutions
long int Number_of_solutions(long int NUMBER){
   long int counter = 0;
   for (long int len = 1; len * (len + 1) < 2 * NUMBER; len++) {
      double p = (1.0 * NUMBER - (len * (len + 1)) / 2) / (len + 1);
      if (p - (int)p == 0.0)
      counter++;
   }
   return counter;
}

// main program goes here
int main(){
   long int NUMBER = 15;
   cout << "Number of ways to write 15 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   NUMBER = 10;
   cout << "Number of ways to write 10 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   return 0;
}

Sortie

Lorsque vous exécutez le programme C++ ci-dessus, il produira le résultat suivant : 

Number of ways to write 15 as a sum of consecutive numbers: 3 
Number of ways to write 10 as a sum of consecutive numbers: 1

Méthode 2 : Méthode d'optimisation

C'est une meilleure approche ; l'approche que nous avons vue ci-dessus provoque un débordement.

La somme de len nombres consécutifs à partir du nombre p peut s'écrire -

sum = (p+1) + (p+2) + (p+3) … + (p+len) 
Hence, sum = (len*(len + 2*p + 1))/2

Parce que sum est également égal au Nombre !.

Nous pouvons écrire

2*Number! = (len*(len + 2*p + 1))

Ici, au lieu de compter toutes les paires (len, p), nous compterons toutes les paires (len, (len + 2*p + 1)). Cela signifie que nous calculerons tous les pf ordonnés (A, B) où AB=2*Number ! Et A< B 且 A 和 B 的奇偶性不同，这意味着如果 len 是奇数，则 (len + 2*p + 1) 是偶数，如果 len 是偶数，则 (len + 2*p + 1) 是奇数。

Cela signifie que nous recherchons des diviseurs impairs de 2*Nombre ! C'est aussi le diviseur impair du Nombre !

Calculez le nombre de diviseurs ! , il faut calculer les puissances des nombres premiers en factorisation, le nombre de diviseurs est (f1 + 1)*(f2 + 1)* … *(fn + 1).

Nous utiliserons la formule de Legendre pour calculer la puissance maximale d'un nombre premier dans la factorielle d'un nombre.

Exemple

Le code de cette approche est donné ci-dessous -

#include <bits/stdc++.h>
using namespace std;
#define maximum 5002
vector<int> v;
void sieve(){
   bool Is_the_number_prime[maximum];
   memset (Is_the_number_prime, true, sizeof(Is_the_number_prime) );
   for (int prime = 2; prime * prime < maximum; prime++) {
      if (Is_the_number_prime[prime] == true) {
         for (int iterator = prime * 2; iterator < maximum; iterator += prime)
         Is_the_number_prime[iterator] = false;
      }
   }
   for (int prime = 2; prime < maximum; prime++)
   if (Is_the_number_prime[prime])
   v.push_back(prime);
}
long long int calculate_largest_power(long long int a, long long int b){
   long long int c = 0;
   long long int x = b;
   while (a >= x) {
      c += (a / x);
      x *= b;
   }
   return c;
}
long long int modular_mult(long long int a,
long long int b,
long long int m){
   long long int result = 0;
   a = a % m;
   while (b > 0) {
      if (b % 2 == 1)
      result = (result + a) % m;
      a = (a * 2) % m;
      b /= 2;
   }
   return result % m;
}
long long int no_of_ways(long long int n,
long long int m){
   long long int answer = 1;
   for (int iterator = 1; iterator < v.size(); iterator++) {
      long long int powers = calculate_largest_power(n, v[iterator]);
      if (powers == 0)
      break;
      answer = modular_mult(answer, powers + 1, m)%m;
   }
   if (((answer - 1) % m) < 0)
   return (answer - 1 + m) ;
   else
   return (answer - 1) ;
}
int main(){
   sieve();
   long long int n = 4, m = 7;
   cout << "Number of solutions after performing modulo with 7 is " <<no_of_ways(n, m);
   return 0;
}

Sortie

Lorsque le programme C++ ci-dessus est exécuté, il produira le résultat suivant : 

Number of solutions after performing modulo with 7 is 1.

Conclusion

Dans cet article, nous avons discuté de deux manières différentes de connaître la factorielle d'un nombre comme la somme de nombres naturels consécutifs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!