Thread: Factorial calculation optimization

For a problem I'm working on, I need to calculate some very, very large factorials; or at least the first five non-zero digits of said factorial. I've worked out the function:

F(n) = (^(n!)/_(10^S5(n)))%10⁵


S₅(n) = ec6eb4f9e17c320d12784365efaad220.png where p = 5 to get the trailing zeros of the factorial.

The Algorithm:

public static void main(String[] args) {
		// TODO Auto-generated method stub
 
		Timer t = new Timer();//just a timer, can be replaced with long start = System.currentTimeMillis();
		t.start();//^
		long fact = 1;//variable containing the needed value
		long limit = (long) 100000.0;//the nth factorial
 
		long pow10 = 10;//powers of 10
 
 
 
		for(long i = 2; i <= limit; i++)//for loop to calculate the needed factorial
		{
				fact*=i; // (i-1)! * i = i! at that point
 
				while(fact%10==0)//does the fact/10^(s_5(i)) function to strip the trailing zeros
					fact/=10;
 
				fact %= 100000;// does the modulus to keep the numbers in bounds 
				if(i%pow10==0)//simply prints out the factorial of powers of ten
				{
					pow10*=10;
					System.out.println(i + ": " + fact);
				}
			//System.out.println(i + ": " + fact);
		}
 
		System.out.println(fact);//print the result
 
		t.end();//ends the timer and prints out the result
		t.printElapsedTimeSeconds();//can be replaced with System.out.println("Elasped time: " + (System.currentTimeMillis()-start)/1000 + " seconds.");
 
 
	}

I can't use De Polignac's formula because the required sieve would take too much memory and brute forcing every prime takes too long. This is the output of F(1000000000):

10: 36288
100: 16864
1000: 53472
10000: 79008
100000: 2496
1000000: 4544
10000000: 51552
100000000: 52032
1000000000: 64704
64704
Elapsed time: 13.476 sec.

I need to calculcate F(1000000000000) or F of 1 trillion. This would take a very long time, there has to be some optimization or tweak that I'm missing somewhere.

Ok, well, you can use De Polignac's formula to figure out how many factors of a prime factor there are in n!.

ec6eb4f9e17c320d12784365efaad220.png

Could you also explain this a different way?

So first order of business is to eliminate all of these pairs. An easy way to do this is count up how many times n! is divisible by 5. Since this is always going to be smaller than the number of times n! is divisible by 2, we know that the factor 5 will be the limiting value of the (2,5) pairs.

Then as you're multiplying through, if a value is divisible by 2/5 and you haven't reached the limiting value for that number, divide the value by the appropriate value.

For example, let's take 10!:

There are two 5 prime factors of the result (5, 10).

Then as we multiply through, removing factors of 2 up to the limit:

num = 1
num = num * 2 / 2, two_count = 1
num = num * 3
num = num * 4 / 2, two_count = 2
num = num * 5 / 5, five_count = 1 (not actually necessary to keep track of five_count since every factor of 5 will be removed)
num = num * 6
num = num * 7
num = num * 8
num = num * 9
num = num * 10 / 5, five_count = 2 (not actually necessary to keep track of five_count since every factor of 5 will be removed)

This is a project Euler problem, so there is a solution possible that takes less than a few minutes possible. I noticed that there are a few thousand final five values under 100000! that have quite a few repetitions, so that says to me that there may be a way to predict when and where those repetitious values come up.

Problem 160 - Project Euler

Problem 160. I've been working on it for a while. First attempt was to brute force the factorial using JScience's LargeInteger class and huge multi-threading. That took too long. Then I moved to trying De Polignac's algorithm specifically, but brute forcing prime numbers took too long and a large enough sieve is impossible to do in Java. This is the only method that's come close to what's needed. I then noticed that there were last-five-digit-combos that never came up, and a whole lot that came up quite often. That's probably the key to figuring out the solution, but I don't know how to apply it.