Large factorial division

1.2k Views Asked by At

If I want to divide $n!$ by $c^x$ but without simply inputting all in a calculator, what would be the best way to do so?

Some example: There are $25!$ atoms on a table. Each second $11^9$ are swept away. How many seconds does it take until all atoms are gone?

EDIT: Looking for a more pen and paper approach.

3

There are 3 best solutions below

3
On

$$\frac{25!}{11^9}=\frac{25}{11}\frac{24}{11}\frac{23}{11}\frac{22}{11}\frac{21}{11}\frac{20}{11}\frac{19}{11}\frac{18}{11}\frac{17}{11}16!$$

If you calculate all the fractions first, then multiply by 16!, then you might not overflow your calculator. It's still a huge number, 16 digits before the decimal point.

0
On

You have to think about what you mean by the "best" way. Avoid arithmetic overflow or underflow? Reduce round-off error? Press fewer buttons? In general, numerical computation has a number of issues that affect the result.

Since you've asked for a pen and paper approach, a good way to "simplify" your result may be to write $$ \frac{25!}{11^9}= \frac{25\cdots22\cdots11\cdots1}{11\cdots11}, $$ where the denominator is the product of nine $11$s. You can cancel two of the $11$s in the denominator with the $11$ and $22$ in the numerator, leaving a $2$ instead of $22$ (since $22=2\cdot11$). Unfortunately, since $11$ is a prime number, this all the cancellation that's possible.

Edit: You mentioned in a comment to another answer that approximations are fine, so I may have mistaken what you meant by a "pen and paper" approach. Logarithms and Stirling's approximation are good ideas, but there are still numerical issues, so you may need to better define what you mean by the "best" way.

2
On

By brain kicked in:

$\log(\frac{16!}{11^9}) = \log(x)$

$\log(16!)-\log(11^9) = \log(x)$ use Stirling's approximation on the factorial and solve for x.