# Last $3$ digits of addition, Olympiad problem.

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!

• The pattern is 2n-1 ! So 2014 isn't included ! And 2016 just added to confused the candidates becuz it is in grade 10 exercise Apr 20, 2017 at 4:28
• You seem to have already figured out that you don't need to care about $n!$ for $n \ge 15$. So just compute the last three digits of $n!$ for $n=1,3,\ldots,13$ and add them up. Apr 20, 2017 at 4:31
• So, there is only one way to do it !? It doesn't related to the fumula 2n-1 !? Apr 20, 2017 at 4:33
• Becuz I don't really want to multiply a lot of digits XD ! If there is an easy way to solve XD Apr 20, 2017 at 4:33
• 1000 divides n! For all n >= 15 so you only have to find the last three digits of 1!+3!+5!+7!+...+13! Apr 20, 2017 at 7:55

## 1 Answer

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.

• Thank you sir! What if the problem is 1!+2!+3!+...+2016!. We have to add up to 14! And it takes really long duration! So I wanna know if we can use the fumula(sigma of n!) to find the last 3 digits ! Apr 20, 2017 at 4:40
• @NovemberftBlue: How much time do you get per problem? They try to size the computation to the time limit. Do you know the small factorials? Even if you only know up to $5!=120$ you are down to two digit already. Doing this up to $14$ wouldn't take long. You are down to a single digit once you pass $9$ so you only need your times tables. Apr 20, 2017 at 4:43
• @NovemberftBlue You are welcome! Also, I am not aware of the formula which you are considering (summation of $n!$). If it is easily computable, certainly we are in a good position to take the remainder when we divide by $1000$. If you like, I will attempt the second variation also. Apr 20, 2017 at 4:48
• Please see the edit. Also, while I am extremely pleased, calling me Sir will be disrespecting the many people better than me on this website. You should keep it for them. Also, I am not in tenth grade yet, so I am younger than you. Hence I should call you Sir, if at all. Apr 20, 2017 at 5:03
• The only formula I know for sum of factorials is this one: math.stackexchange.com/questions/301615/… , but I don't think it applies here.
– N74
Apr 20, 2017 at 5:23