c++ large numbers in factorial

Question

I am trying to make a program with the problem "Given a positive integer a, what is the minimum positive integer g such that g! is a multiple of the square of a!?

Sample Input

1 (test case)

4

Sample Output

8

Explanation: 8!=40320 is divisible by 4!^2=24^2=576. Furthermore, it is the smallest one because 7!=5040 is not divisible by 576.

The program is successful, but i'm having trouble when the input is larger than about 20. It wont output anything.

Any suggestions?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
long long a,b,c=1,d,e=1,f=1,g=0,k;
cin>>a;
while(a>0){
    cin>>b;
    g=0;
    e=1;
    c=1;
    f=1;
    for (long long i=1; i<=b; i++){
        c=c*i;
    }
    d=c*c;
    for(long long j=1; e!=0; j++){
        f=f*j;
        g=g+2;
        e=f%d;
        if(c==e)
        cout<<g<<endl;
    }
    a--;
}
return 0;

}

21! is greater than 2^63 (long long) which gives you integer overflow problem. You will have to either devise a method to strip trailing zeros from factorials or write a custom big integer class — Tomasz Plaskota, Nov 19 '16 at 17:31
*Any suggestions* -- Yes -- Use [boost](http://ideone.com/Y8A8Is). Same code (except for the output of the actual factorial and the usage of `cpp_int`). — PaulMcKenzie, Nov 19 '16 at 18:07

score 0 · Answer 1 · answered Nov 19 '16 at 18:08

Brute force will lead to integer overflow for all inputs whose value is more than 20. I got a better solution of this problem whose time complexity is O(T) where T = number of test cases and it uses constant space.

Solution : Value of g will be equal to 2*afor all a.

         (a!)^2 = (a!)*a*(a-1)*(a-2)*..3*2*1

Our aim is to make (a!)*a*(a-1)*(a-2)*..3*2*1 in the form of g! by multiplying with minimum possible integer required to do so.

If we multiply 2 with each of a,a-1,a-2,...,3,2,1, then we will get

        (a!)*2a*(2a-2)*(2a-4)*..6*4*2

This is too close to become factorial of an integer. Now it's trivial to make it equal to 2*a!.

Till now we got a number which is divisible by (a^2)! but we don't know whether this will be minumum such integer or not.

This 2a will be minimum such number as you have twice 1s,2s,3s,4s,...,ns in (a^2)! and all these should be present in g! as (a^2)! divides g!. This argument proves that 2*a is the minimum such integer.

With a=6, g=10 works. `2a` is the _maximum_ value to consider for `g`, In select cases, `g` may be less. — chux - Reinstate Monica, Nov 19 '16 at 18:12

chux - Reinstate Monica · Answer 2 · 2016-11-19T18:24:50.320

Any suggestions?

Avoid wide math.

It certainly appears g >= a, so ....

a! is a factor of g! and a! is a factor of square(a!), so we can simplify the problem. Divide both side by a!

g!/a! = 1 *  a+1 * a+2 * ... * g
square(a!)/a! = a!

Now find smallest g such that (a+1 * a+2 * ... * g) % a! == 0

Each of these a+1, a+2, ..., g terms may have factors in a!. A solution must be found by the time g reaches 2a, but maybe sooner. As each term is found, factor it out of a! and test for mod-ness This keeps the need for wide integer to a minimum.

Something like the following. Unfortunately I can not test it out right now. IAC, OP was looking for suggestions, not code.

unsigned SOPP_LargeFactor(unsigned a) {
  unsigned i = 1;
  unsigned long long prod = 1;
  for (unsigned g=a+1; ; g++) {
    prod *= g;
    while (prod%i == 0) {
      if (i == a) return g;
      prod /= i;
      i++; 
    }
  }
}

score 0 · Answer 3 · answered Nov 20 '16 at 17:09

g!= k·a!². After some descomposition, k=(a+1)(a+2)...g / (2*3*4...a)

If k is integer this means that it's possible to find divisions with also an integer result. More, ALL divisions must be integer.

First, decompose numerator and denominator into prime factors. I.e. 7! = 7·6·5·4·3·2= 7·5·3²·2⁴

Then, if g is a solution, ALL denominator factors must be found also in the numerator (e.g. 3⁵ in numerator includes 3² in denominator), and thus can be cancelled. Multiplying the remaining factors in numerator just give us k, which is not needed.

You can set a loop to test several g until this condition is met. I'd store primes and their exponent so cancelling is a matter of decreasing exponents.

Last, no Big Number calculations are involved. g is only limited by sizeof(long).

c++ large numbers in factorial

3 Answers3