Back to problem set

Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.

Problem 1

Find the units digit (base 10) in the sum $\displaystyle{\sum_{k = 1}^{99} k!}$.

Hints

Hint #1

Can you think of any shortcuts here so that you don’t have to manually compute each and every term’s value?

Hint #2

Do you need to actually compute each full $k$ term? Does it matter?

Solution

Open to see the solution; try solving it first or see the hints above!

Since we need to find the units digit in base 10 of the sum $\displaystyle{ \sum_{k=1}^{99} k! }$, we are really trying to find $\displaystyle{ \left( \sum_{k=1}^{99} k! \right) \mod 10 }$.

First, we note that only the units digit of each term $k!$ has an influence on the units digit of the sum; in other words, we can consider just summing up each term’s units digit and then take the final digit of the sum:

$$ \left( \sum_{k=1}^{99} k! \right) \mod 10 = \left( \sum_{k=1}^{99} ( k! \mod 10 ) \right) \mod 10 $$

The reason this is valuable is that we don’t want to compute each $k!$ term, but we can find that many terms are $0 \mod 10$ because they include $10$ as a factor, so we can just ignore them entirely.

Since $k! = k \times (k-1) \times \cdots \times 1$, any term $k \ge 10$ can be excluded since $10 \cdot x \equiv 0 \mod 10$ for any $x$. Thus, we can exclude all terms in the interval $[10, 99]$ and can just compute the units digit of the terms in the interval $[1, 9]$.

However, we can save ourselves even more effort because $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \equiv 0 \mod 10$ because it includes both terms $5$ and $2$. Thus, we can further exclude all terms $k \ge 5$, so we eliminate the interval $[5, 9]$ as well, and we are just left with:

$$ \begin{align*} 1! + 2! + 3! + 4! \mod 10 & = 1 + 2 + 6 + 24 \mod 10 \\ & = 33 \mod 10 \\ & \equiv 3 \mod 10 \\ \end{align*} $$

Thus, the units digit of the overall sum is $\boxed{ 3 }. \enspace \blacksquare$

Verification

This includes the answer; try solving it first or see the hints above!

Since Python supports arbitrarily-sized integers, we can easily verify this directly:

$ python
>>> import math
>>> sum([math.factorial(k) for k in range(1, 100)]) % 10
3

Note that Python’s range(x, y) function creates a half-open interval $[x, y)$:

>>> list(range(1, 10))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Thus, range(1, 100) is what we need to represent $\displaystyle{\sum_{k = 1}^{99}}$ above.