Express factorial n as the sum of consecutive numbers

We will discuss two methods to find out how to express the factorial of a number as the sum of consecutive numbers. The first method is the direct and simple method, while in the other method we use the concept of arithmetic progression to make it less complex in terms of time and space occupied.

Problem Statement

Given a number, we need to find a way to express the factorial of the number as the sum of consecutive natural numbers.

This involves two different functions -

• Find the factorial of a number.

• Find the number of ways in which a number can be represented as the sum of consecutive natural numbers.

Example 1

Given : Number = 3
Result: 1

As we all know, the factorial of 3 is 6, which can be written as 1 2 3, so our answer is: 1 way.

Example 2

Given: Number = 4
Result: 1

As we all know, the factorial of 4 is 24, which can be written as 7 8 9, so our answer is: 1 way.

method 1

This is a simple method, we first find the factorial of a number and then calculate the number of ways in which it can be expressed as the sum of consecutive natural numbers. The method is to express the factorial as a series of arithmetic length len 1 as -

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

When we obtain len as a positive integer, we treat it as a solution.

Example

In the following example, we try to find the number of ways to express the factorial of a number as the sum of consecutive numbers.

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

Output

When you run the above C program, it will produce the following output -

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

Method 2: Optimization method

This is a better approach; the approach we saw above causes overflow.

The sum of len consecutive numbers starting from the number p can be written as -

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

Because sum is also equal to Number!.

We can write

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

Here, we will count all (len, (len 2*p 1)) pairs instead of counting all (len, p) pairs. This means we will compute all ordered pf (A, B) where AB=2*Number! And A< B 且 A 和 B 的奇偶性不同，这意味着如果 len 是奇数，则 (len + 2*p + 1) 是偶数，如果 len 是偶数，则 (len + 2*p + 1) 是奇数。

This means we are looking for odd divisors of 2*Number! This is also the odd divisor of Number!

To calculate the number of divisors! , we must calculate the powers of prime numbers in factorization, the number of divisors is (f1 1)*(f2 1)* … *(fn 1).

We will use Legendre's formula to calculate the maximum power of a prime number in the factorial of a number.

Example

The code for this approach is given below -

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

Output

When the above C program is run, it will produce the following output -

Number of solutions after performing modulo with 7 is 1.

in conclusion

In this article, we discussed two different ways to find a number, expressing the factorial of a number as the sum of consecutive natural numbers.

The above is the detailed content of Express factorial n as the sum of consecutive numbers. For more information, please follow other related articles on the PHP Chinese website!