1,000,000!

Dross · 2007-01-14 00:27:57

This weekend boredom beset me so I went about calculating 1,000,000! (one million factorial).

The number is in a text file, but I can't upload it to geocities (I think it's too large - it'll upload smaller files, but won't give a reason for not uploading this one). The unformatted .txt file is 5.31 MB in size.

Some stats:

1,000,000! has 5,571,271 digits
The last 249,998 digits are zero
In Microsoft Word, with size 10 courier new font, the number takes up 69,641 lines and 1,142 pages
It took 6 hours, 26 minutes and 43 seconds to compute on my machine (2.55 GHz Celeron processor with 1 GB of ram)

The number wasn't calculated by any approximation - sheer brute force was used, so I'm sure it's correct. I'd be happy to send it to someone to put on a website. I'm not sure how large a file I can attach on hotmail though... anybody got any ideas?

Anyway - such are the fruits of my weekend's labour!

Last edited by Dross (2007-01-14 00:28:32)

Toast · 2007-01-14 00:33:55

Wow, great job Dross! What did you use to calculate it? I'm looking forward to seeing it.

(Courier New is a pretty big font )

Devantè · 2007-01-14 00:39:48

Sounds interesting.

Maybe you could upload it on rapidshare.

Dross · 2007-01-14 01:16:44

Toast wrote:

What did you use to calculate it?

I wrote a simple program in java. It doesn't just go through one number at a time and update a single variable (i.e. doesn't just compute 1 x 2 x 3 x 4 x 5... straight out) - instead it splits 1,000,000 into sections, so it behaves more like it's doing 1 x 2 x 3 x 4, then 5 x 6 x 7 x 8... and so on, then multiplies the results of all those calculations together. This just makes the program a lot faster because it doesn't have to deal with any ridiculously large numbers until right at the very end of the program when it computes the final result - but it's a crude (uncalculated) optimisation. It could probably be made a lot, lot faster if I took the time to work out how to make it so!

I've never used RapidShare before - I uploaded it and the info on it says "DownloadLink: http://rapidshare.com/files/11657189/1000000Factorial.txt.html" if anybody wants to get at the file.

Don't bother loading it into WordPad - the number has no carriage returns so all the digits go on one line, and it won't let you scroll to the end!

mathsyperson · 2007-01-14 01:25:38

I couldn't get at the file. Rapidshare said that I'd reached the download limit for free users, even though I'd never used it before.

I can confirm that 1000000! ends with 249,998 zeroes though. That's the number of factors of 5 that all the numbers from 1 to 1000000 have. (200000 have one, then 40000 have another one, then 8000 have another, 1600 have another, then 320, then 64, then 12, then 2. 200000+40000+8000+1600+320+64+12+2 = 249,988)

Factors of 2 occur more often than factors of 5, and so for every factor of 5, there will always be a factor of 2 that pairs with it. 2x5 = 10, so there are equal amounts of factors of 5 and factors of 10. And for each factor of 10, the number ends with a 0.

I predict (bearing in mind that I couldn't get at the file) that the first number of 1000000! is a 1.

Dross · 2007-01-14 01:29:17

Alas! The first number is a 3 - it starts off as:

33502795642050604570356757263394648029746124002153075734328879430431840303897445247126830355...

Was 1 a blind guess, or was there rhyme & reason behind it?

Anyway, in a bit I'll post the source code so anybody who wants to can verify that. (I'll comment it so it'll make sense to someone else first )

mathsyperson · 2007-01-14 01:50:58

Kind of a bit of both. While you'd expect there to be a 1/9 chance of the first number being a 1, the chance is actually closer to about 30%.

The distribution of all numbers anywhere is not uniform. The probability of any number's first digit being N is given by log(N+1) - log(N). If you look in a newspaper, or any other place that contains numbers, you'll notice that significantly more of them start with 1 than with 9. I'm not entirely sure why that is, but it certainly works.

So, it was kind of an educated blind guess. I had around a 30% chance of being right, but if I was then you'd think that I'd only had 1/9 chance and so it would have seemed slightly more amazing than it was. It was worth a try.

Dross · 2007-01-14 11:19:22

Here's the source code - if anyone wants to double check it (or reproduce it in any non-money making capacity), feel free.

import java.io.*;
import java.math.BigInteger;

public class Tester {
    
    public static void main(String[] args) {
	
	PrintWriter out = null;        // to print out the result
	
	try {
	    out = new PrintWriter(
		new BufferedWriter(
		    new FileWriter("C:\\Factorials.txt")));
	} catch (IOException e) {
	    e.printStackTrace();
            System.exit(0);
	}
	
	int numToFactorial = 1000000;  // one million
	
	    // first, compute 1000!, 2000!/1000!, 3000!/2000!...
	    // and put into a BigInteger[]
	BigInteger[] products = new BigInteger[1000];		// 1000 = sqrt(1000000) (arbitrary choice)
	
	for (int i = 0, n = 1 ; i < products.length ; i++) {      // n denotes the next number to multiply by to get a factorial
	    products[i] = new BigInteger(n + "");
	    
	    for (int j = 0 ; j < (numToFactorial / products.length) ; j++, n++) {
		products[i] = products[i].multiply(new BigInteger(n + ""));
	    }
	}
	
	    // reduce products to a smaller array (arbitrary size - intended for quicker computation)
	BigInteger[] products2 = new BigInteger[4];
	
	for (int i = 0, p = 0 ; i < products2.length ; i++) {     // p denotes index of products[]
	    products2[i] = BigInteger.ONE;	    // start off with one - makes the next for loop neater
	    
	    int x = products.length / products2.length;	    // so we don't have to calculate it every time
	                                                    // in the next for-loop (to speed things up)
	    
	    for (int j = 0 ; j < x ; j++, p++) {
		products2[i] = products2[i].multiply(products[p]);
	    }
	}
	
	    // for the final answer
	BigInteger product = BigInteger.ONE;
	
	for (int i = 0 ; i < products2.length ; i++) {        // this loop will take LOTS of time
	    product = product.multiply(products2[i]);
	}
	
	out.print(numToFactorial + "! = " + product);
	
	out.close();
	
    }
    
}

I'm uploading a text file containing the number at the moment. My computer ain't liking it

Dross · 2007-01-14 11:27:19

Right - there are two files, each containing roughly one half of the digits of the number (the whole thing was too big for yahoo to deal with).

Part 1
Part 2

Math Is Fun Forum

#1 2007-01-14 00:27:57

1,000,000!

#2 2007-01-14 00:33:55

Re: 1,000,000!

#3 2007-01-14 00:39:48

Re: 1,000,000!

#4 2007-01-14 01:16:44

Re: 1,000,000!

#5 2007-01-14 01:25:38

Re: 1,000,000!

#6 2007-01-14 01:29:17

Re: 1,000,000!

#7 2007-01-14 01:50:58

Re: 1,000,000!

#8 2007-01-14 11:19:22

Re: 1,000,000!

#9 2007-01-14 11:27:19

Re: 1,000,000!

Board footer