Last $3$ digits of addition, Olympiad problem.

Question

Find the last three digits of the following: $$1!+3!+5!+7!+\ldots+2013!+2015!+2016!$$ I have tried to divide by $1000$ up to $15!$, but the number is too high and confused. So I wanna know if there is other way to solve this problem. Thanks in advance!

Answer 1

You can work via modular arithmetic, simplifying mod $1000$ after each step.

$1! = 1, 3! = 6, 5! =120$.

$7! = 7 \times 6 \times 5! = 5040 \equiv 40 \mod 100$ (by computation)

$9! = 9 \times 8 \times 40 \equiv 880$ (here we do not have to compute $9!$).

$11! = 11 \times 10 \times 880 = 11 \times 800 \equiv 800 $

$13! = 13 \times 12 \times 800 = 13*600 \equiv 800$

$15!$ is a multiple of $1000$, and so are the others after this, so the answer would be $800 + 800 + 880 + 40 + 120+6+1 = 647 $ modulo $1000$. Important to note that no factorial above $7!$ was computed explicitly.

Note : You cannot avoid simple computations. All the above computations were atmost of four-digit complexity.

Wolfram verifies the the sum up to $13!$ as $6267305647$, so the above answer is correct.

---

EDIT : About the question asked in the comments, we have to essentially compute $1! + ... + 14!$ modulo $1000$. Again, we can work by hand :

You will get, by hand, the sum up to $6!$, as $720 + 120 + 24 + 6 + 2 +1 = 873$.

Now, it is a question of computation and reduction:

$7! = 7\times 6! = 5040 = 40$

$8! = 8 \times 40 = 320$

$9! = 9 \times 320 = 2880 = 880$

$10! = 10 \times 880 = 8800 = 800$

$11! = 800 \times 11 = 8800 = 800$

$12! = 800 \times 12 = 9600 = 600$

$13! = 600 \times 13 = 7800 = 800$

$14! = 800 \times 14 = 11200 = 200$

Now, add these up : $100(8+8+8+2+6) + 880 + 320+40+873 = 273$ (after reduction).

However, I would feel sympathetic if you were allotted four minutes for this question. Probably it is worth more marks than the others, but that is scant consolation for a problem nearly involving outright computation.

Furthermore, there isn't any sum of factorials formula, by my reckoning, that is capable of producing the remainder mod $1000$ (and if there is some complicated formula involving exponentials and gamma functions, then that is a roof too high for tenth grade, certainly). Hence (unfortunately) this problem is done only by computation.