6
$\begingroup$

Since there are less powers of $5$ than of $2$ and since $10 = 2 \cdot 5$, I counted the number of zeros in $2017!$: $\left \lfloor{ \frac{2017}{5^1}}\right \rfloor + \left \lfloor{ \frac{2017}{5^2}}\right \rfloor +\left \lfloor{ \frac{2017}{5^3}}\right \rfloor +\left \lfloor{ \frac{2017}{5^4}}\right \rfloor = 502$

Now I need to find $\frac{2017!}{10^{502}} \pmod{10^5}$

Using Chinese remainder theorem I split the $\pmod{10^5}$ into $\pmod{2^5}$ and $\pmod{5^5}$. Since there are a lot more powers of $2$ left, $\frac{2017!}{10^{502}}\equiv 0 \pmod{2^5}$

I am having trouble with getting $\frac{2017!}{10^{502}} \pmod{5^5}$. What would be the best way to compute it?

Clarification: significant digits - the ones that follow up before the zeros at the right side of the number.

$\endgroup$
3
$\begingroup$

OK, for what it's worth, the answer can be derived by casting out all factors of $5$ and multiplying the resulting numbers incrementally $\bmod 100000$, which also allows us to also divide out from the running product the same power of $2$ as the power of $5$ that we just cast out.

As a way of checking any more elegant mathematical approach, therefore, the result is

$15968$



As an aside, I'll share the process I used to calculate this and justify a shortcut that I used.

The basic idea here was to multiply successive numbers into a running product, excluding powers of $5$ and adjusting powers of $2$. The process for each number was:

  • find the highest power of $5$ that divides the new number
  • divide that out of the number
  • multiply the adjusted number into the running product and divide by an equivalent power of $2$
  • find the residue $\bmod 100000$

Note that this gives identical running $\bmod 100000$ values to @skyking's approach.

There is a intermittent problem with this approach, in that the running product will potentially be wrong for a couple of numbers after a large power of $5$ is divided out. Effectively, the value should be saturated with factors of $2$ from $8!$ onwards, but dividing out a suitable power of two may disturb this briefly. For example, the value for $15!$ is out in this process - $24368$ instead of the correct value, $74368$. Nevertheless, once a suitable number of factors of two in subsequent numbers are multiplied back into the product, the $\bmod 100000$ value gets back on track.

$2017$, occurring as it does directly after $2016$ = $2^5\cdot 63$, has an accurate running product by this method.

An continuously accurate running value can be produced, if necessary, by building up a "reserve" of a few powers of $2$ separately from a running product calculation, by stripping out powers of two from the successive values until the reserve is full. This is then used to compensate for powers of $5$ encountered, and multiplying these back in to the reduced running product. This correct gives the value for $15$ etc.

$\endgroup$
1
$\begingroup$

It's quite straight forward to calculate (and you don't have to figure out the number of trailing zeroes ahead of calculations). One could of course compute $2017!$ and take the last five significant digits.

However one could simplify the calculation by dividing away trailing zeroes and only keep the lower significant digits, but in doing so one have to take some care not to loose significant digits. Better way is to note that every time we get a zero at the end is because of a factor two and five and drop these factors pairwise. So we simply can for example defer the factors two and five and then at the end drop them pairwise and only keeping the factors two that are left.

To illustrate, after five steps we have:

$$1\times2\times3\times4\times5 = 24\times 5^1$$

here the last $5^1$ is to keep in mind the number of factors five we have to handle in the end.

$$24\times5^1\times6\times7\times8\times9\times10=36288\times2^1\times5^2$$

the next step is:

$$36288\times2^1\times5^2\times11=399168\times2^1\times5^2$$

now $399168>99999$ so we take modulo $100000$ and get to get $99168\times2^1\times5^2$ and continues...

$\endgroup$
  • $\begingroup$ Wait, what? You did all 2017 calculations?!?!?! $\endgroup$ – fleablood Jul 28 '16 at 23:54
  • $\begingroup$ When we reduce mod 100000 and later divide by 10, how can we know the reduction didn't lose significant information? $\endgroup$ – Christian Sievers Jul 28 '16 at 23:59
  • $\begingroup$ @fleablood Yes, I did - you can easily do that by writing a python program for it... $\endgroup$ – skyking Jul 31 '16 at 10:03
  • $\begingroup$ @ChristianSievers You're absolutely right - I have modified the algorithm to take care of that problem. It's quite similar to Joffans answer and maybe his description is a bit simplier. $\endgroup$ – skyking Jul 31 '16 at 10:17
-1
$\begingroup$

I know how to do the last 3 significant digits, if that helps.

$4! = 24\\ \frac {9!}{5!} = 3024 \equiv 24\pmod {1000}$

$\frac {5n!}{5^n n!} = 24^n \pmod {1000}$

$2017! = \frac {2017!}{2015!}\frac {2015!}{5^{403}403!}\frac {5^{403}403!}{5^{80}80!}\frac {5^{80}80!}{5^{16}16!}\frac {5^{16}16!}{5^{3}3!} 3!\\$

$\frac {2017!}{10^502} \equiv 12^{502}\frac {2017!}{2015!}\frac {403!}{400!}\frac {16!}{15!}3!\pmod{1000}$

$144\cdot17\cdot16\cdot403\cdot402\cdot401\cdot16\cdot6 = 968\pmod{1000}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.