If you’re not a math geek, you probably don’t want to go any further.
Does anyone know of a way to calculate a factorial (n!), where n is a huge number? I’ve got a case where n = 55556, and no method that I’ve found will calculate that.
Stirlings number won’t do it, because one of its factors is (n/e)^n, which is too big to get anything except a notice that the answer is ~infinity.
Thanks in advance for any ideas that you have.
For what purpose do you need this calculation? And relatedly, in what format would you like the answer expressed? Any answer we give must necessarily take both of these questions into account. For instance, we could give you an answer in scientific notation with a few digits of precision, but we’d be losing a bunch more digits. Is that good enough? Is it good enough to just say whether it’s larger or smaller than some other number? Is it enough to just express the answer as “55556!”, which is completely correct?
Arbitrary precision calculator (input “factorial(55556)”).
I’m trying to calculate the number of 5 digit numbers that can be formed out of a series of numbers that is 55556 long. An answer to three or four significant digits given in exponential notation is just fine. The formula in question is:
number of combinations = n!/((r!*(n-r)!)
Rather than mess around with factorials, would a calculator that gives you combinations directly do what you need? See if [this one](http://stattrek.com/online-calculator/combinations-permutations.aspx\) works for you. Or there’s always WolframAlpha.
Or were you more curious about the how, rather than just getting results?
Keep in mind that n! / (n-r)! = the largest r terms in the expansion of n!. In this case, 55556! / 55551! = 55556 * 55555 * 55554 * 55553 * 55552. That’s easily within the capabilities of even 1980s calculators. I’ll leave the rest to you/Wolfram/etc.
By the way, W|A says 55556! is roughly 2.404 x 10^239473.
OK, so let’s take Stirling’s Formula:
ln(n!) ~ n ln(n) - n + O(ln(n))
Plugging in n = 55556, we find that ln(n) = 10.925…, and so n ln(n) = 606957.5… . We really ought to include the O(ln(n)) term, even though 11 << 60,000, since this is a log, but I’ll leave that as an exercise for the student, and just say that ln(n!) ~ 551,000.
OK, now, you say that this doesn’t help us, because your calculator can’t handle exp(551,000). But it doesn’t need to. We want the answer in scientific notation anyway, which means we don’t want exp(551,000); we want log[sub]10/sub. And that’s easy, even with an ordinary eight-digit calculator. From your basic log identities, log[sub]10/sub = 551,000/ln(10) , or 239,000 . In other words, n! ~ 10^239,000 .
Now, if I had a figure for ln(n!) that I trusted to more digits (i.e., to a few places after the decimal point), I could do better than this, and get something in the form of x*10^y. I’d first find the base-10 log, as above. Then, I’d take the integer part and the fractional part of that number. The integer part would give me the 10^y part of the answer, and 10^(fractional part) would give me the x part.
Yeah, just remember that everything cancels out after the 55552. (So something like 6!/3! = 654321/321, canceling out the 321 part (with the 1 being unnecessary), so you just get 654. In the OP’s equation, it’s (like you say) 5555655555555545555355552, since everything that follows will be cancelled out. The answer is 529 147 406 295 998 111 569 920. (ETA: for 55556!/55551!).
Usually you’ll be happy to work with the logarithm of the factorial. That is approximated readily with Stirling’s formula:
log n! = (n + ½) * log n - n + .92
where the final two terms are likely to be irrelevant for useful back-of-the-envolope calculations.
This leads to, taking logs base 2, for n ≫ r ≫ 1
log C(n,r) ≈ r * (log n - log r + 1.44)
(1.44 = log[sub]2[/sub] 2.71828)
Don’t know if Wolfram Alpha is a method you’d like but here’s a link.
As others have mentioned, modern bignum (multiple-precision integer, that is) libraries will handle it no problem as long as you have enough RAM on your system to hold the final result and whatever intermediate results are required. I wrote a factorial program in Haskell which did it just fine; the result was (lemme check again…) 239,483 digits long, but that’s just not very big when your computer has eight gigs of RAM. And eight gigs of RAM isn’t very much these days.
So… I could email you the number, I suppose.
(Technical details: Glasgow Haskell Compiler, so the program uses the GNU Multiple Precision Arithmetic Library. It’s written the naive way, with a foldr function as opposed to actual recursion, but the above computation still completes in barely over a second wall-clock time.)
Also note that there is a lesser-known notation, the Pochhammer symbol, specifically for this case. Basically you are computing (55556)[sub]5[/sub] or equivalently 55552sup[/sup].
Nicely done. Congrats.
It’s amazing just how big of a hammer most of us own these days. If only more people knew how to actually use it. 
Oh, cool, I never knew that. Now I’ll know what the heck that means if I come across it. Is it fairly standard notation, or is it somewhat esoteric?
But, wait. I guess I’m not understanding this correctly. Are you looking for how many unique 5-digit numbers there are? I mean, the theoretical maximum would be 100,000 wouldn’t it (allowing for numbers like 00000). Otherwise, if leading zeroes are not allowed, then 90,000.
Also, if what you’re looking for is just an abstraction and you really want to know how many ways there are to pick 5 items from a pool of 55556, then you have to think about whether the order matters. If it does, then you want to get rid of the r! in the equation above. If it does not, then your equation above is fine (and can also be written as 55556 choose 5, and entered as such in Wolfram Alpha.)
I’d call it “niche”. I encountered it working with generalized hypergeometric functions, which have series expansions with a lot of them in them (and would, sans notation, require a bunch of n!/(n-k)! factors all over the place).
The hipsters all write 1sup[/sup], because n! is “too mainstream”.
Thanks for all your replies. I’ve got some thinking to do now.
Actually, I’ve got an old (but useful) HP32ii hand calculator that has the x! function on it. Unfortunately the calculator had gone AWOL so wasn’t able to see of that one worked. Still looking.
The order doesn’t matter.
Another question. Say you’ve got n=26 (number of letters in the alphabet) and desire to find out the number of six letter words that can be made out of those. If there were no limit on the duplication of letters within the word, that would be simple using the equation, but another limit is that there can be no more than two duplicates in any word. Any ideas?
BTW, this is NOT a homework problem. At my age I’m way beyond that.
That depends on what you mean by “no more than two duplicates”: are you trying to exclude words like “JUBJUB” in which more than two letters each appear more than once, or words like “BANANA” in which any letter appears more than twice?
Anyway, I’d solve the problem by adding up the number of six-letter words with no duplicates + the number of words with one duplicate + the number of words with two duplicates.
To get you started, the number of six-letter words with one duplicate (i.e. exactly one letter appears exactly twice) would be 26 * (25 Choose 4) * (6! / 2!) = 118,404,000:
the number of possibilities for the repeated letter * the number of possibilities for the other four letters * the number of different orders those six letters could be in.
A traditional calculator like that was limited to floating point notation with exponents between + or -99.
So Fact(69) fits at ~1.71E98. But Fact(70) overflows since it’s ~1.19E100. Pretty useless for the scale of numbers you’re interested in.
And those calculators computed the number using floating point math which won’t give you a strictly correct answer.
This is the original question as restated by the OP. It’s still logical gibberish as far as I can see.
If the question is how many distinct 5-digit short strings you can generate by pulling single digits from a long string of 55556 digits, the answer depends totally on what that 55556-digit string consists of. e.g. if the long string is “11111…1111111”, then exactly one unique 5-digit string can be extracted from it: “11111”. There are 55556! distinct ways to generate the short string. But they’re all identical. So the answer is 1, not 55556!
If instead we assume the long string has at least one example of each digit from 0-9, then the number of unique generatable 5-digit short strings is simply 10^5. Assuming of course we can pull the same item (e.g. the digit in place #12345) more than once into our generated substring. If we can’t reuse a long string entry, and there are fewer than 5 of any given digit in the long string then it gets more complicated.
So combinations and permutations are irrelevant to solving the problem as stated. I wonder what problem the OP was really trying to think about?