It is given that
$19!$
equals
$\overline{121\, 645\, 100\, 408\, abc\, 000}.$
Determine the value of
$\overline{abc}$
.
Details and assumptions:
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
This solution was converted from a comment
The mod function doesn't only meant to the remainder, as long as when $a\overline= b\pmod n$ , then $n|a-b$ . As an example, $3 \overline= -1\pmod4$ is correct since $4|3-(-1)$ .
Log in to reply
Yes, you are right. What I meant was that mod function could be used when we are interested in the remainder (in this case).
Hey, I think I don't understand the notation. Shouldnt 19! be equal to 109641728?? Thank you very much :)
Log in to reply
What do u mean?
Log in to reply
Well, this is pretty weird. AFTER reading the solutions proposed by you and Andrew I wrote a simple code to calculate 19! just for fun (I am studying Computer Science). What's weird is that I was sure my code worked (since is very simple) but it returns to me 19! = 109641728. Can someone around here who has some knowledge in programming have a look at my code and tell me what's wrong?
The code: http://pastebin.com/DPb9ysUd
Thank You :)
Log in to reply
@Josep Burgaya Pujols – This is probably because 19! is far to large to fit in a 32 bit number. So if an int is 32 bits on your system, then the number must have overflowed many times.
$\overline{121645100408abc000} = \overline{1216451004508abc} * 1000$
As Given $1216451004508abc*1000=19!$ This implies $\overline{121645100408abc}=2 * 3 * 6 * 7 * 8 * 9 * 11 * 12 * 13 * 14 * 3 * 16 * 17 * 18 * 19$ (as $4 * 5 * 10 * 5=1000$ ) is divided on both sides when we multiply the R.H.S only the last 3 digits contribute to $\overline{abc}$ .
$2 * 3 * 6 * 7 * 8 * 9=1144$
the last 3 digts(144) contribute to
$\overline{abc}$
.
$144 * 11 * 13$
will have last 3 digits 592 now we will multiply further
$592 * 12 * 14$
will have last 3 digits 456 similarly,
$456 * 17 * 19$
will have last 3 digits 288,
$288 * 16 * 18$
will have last 3 digits 944 and finally
$944 * 3$
will have last 3 digits 832 now we have multiplied all the numbers and got the last 3 digits to be 832
[Latex edits]
This solution is featured, even though it is admittedly a "brute force" one, because it can actually be done by hand (try it!) Another way to go is to use various divisibility rules, like 7, 9, 11. This is sufficient since $7 \times 9 \times 11 > 1000$ so the last 3 digits are uniquely determined.
While one can, of course, get the correct numerical answer just by multiplying with a computer of a good calculator, this does not count as a valid solution.
To begin with, let us expand the factorial for illustrational purposes
$19!=1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18\cdot19$
The first thing we should take into account is that $a=b=c=0$ is not a solution to the problem, since then the integer would be evenly divisible by $1000000$ , which is a number that cannot be formed by multiplying solely the numbers included in $19!$ .
Additionally, we may divide the actual integer with $100$ by diving the expanded factorial as well, resulting in losing the integers $10,2$ and $5$ from the expansion (since $2\cdot5=10$ ). Consequently, the integer we are looking for has now acquired the following form
$\overline{121645100408abc0}$
We are now going to use the divisibility rules for $4$ and $8$ .
An integer is divisible by $4$ only if the integer formed of its last $2$ digits is divisible by $4$ .
On the other hand, an integer is divisible by $8$ only if the integer formed of its last $3$ digits is divisible by $8$ .
By using the divisibility rule for $4$ we can easily come to a conclusion that $c\in\{2,4,6,8\}$ , due to the fact that the only $2$ -digit integers that end in $0$ and are divisible by $4$ are $20,40,60$ and $80$ . Similarly, it is also correct that the only $3$ -digit integers that end in $0$ and are divisible by $8$ are $160,240,320,400,480,560,640,720,800,880$ and $960$ . However, taking into account that $c\neq0$ we may disregard the integers $400$ and $800$ .
Let us now turn our attention to the divisibility rule for $11$ , which can be found thoroughly explained here .
By using it, we come to the expression
$((1+1+4+1+0+0+a+c)-(2+6+5+0+4+8+b))\mid11$ $\Rightarrow$ $(a+c-b-18)\mid11$
Now, considering that $1\leq a,b\leq9$ and $c\in\{2,4,6,8\}$ , the minimum of the above expression is $-24$ ( $a=0,b=9$ and $c=2$ ), whereas the maximum is $-2$ ( $a=9,b=1$ and $c=8$ ).
Now, the only integers in the interval $(-24.-2)$ that are divisible by $11$ are $-22$ and $-11$ .
We are now going to implement the divisibility rules for $3$ and $7$ . The one for $3$ states that an integer is divisible by $3$ only if the sum of the digits of that integer is also evenly divisible by $3$ .
Therefore, if the sum of the digits of our integer is $a+b+c+32$ , it is evident that
$3\mid(a+b+c+32)$
The divisibility rule for $7$ can be found here .
We shall now discuss $2$ cases:
Case 1:
$a+c-b-18=-22 \Rightarrow a+c-b=-4$
From the possible numbers stated from the divisibility rule for $8$ (which again, are $160,240,320,480,560,640,720,880$ and $960$ ) the only pair $(b,c)$ that make the above equation at all possible is $(7,2)$ , since $1\leq a\leq9$ .
As a result of that, we can see that
$a-7+2=-4 \Rightarrow a=1$
The possible solutions for $a,b,c$ are $1,7,2$ accordingly. To check if this is indeed true we will use the equation from the divisibility rules for $3$ and $7$ .
Although $1+7+2+32=42$ which is divisible by $3$ , using the divisibility rule for $7$ we come to a conclusion that the integer $121645100408172$ is not divisible by 7, therefore
$a+c-b\neq-4$ , which proves this case wrong.
Case 2:
$a+c-b-18=-11 \Rightarrow a+c-b=7$
From the possible numbers stated from the divisibility rule for $8$ (which again, are $160,240,320,480,560,640,720,880$ and $960$ ) the pairs $(b,c)$ that make the above equation at all possible are $(1,6),(2,4),(3,2),(4,8)(5,6),(6,4),(8,8)$ for $a\in\{2,5,8,3,6,9,7\}$ accordingly, since $1\leq a\leq9$ .
Using the divisibility rule for $3$ , we may exclude all possible solutions for $a,b,c$ apart from $a=8,b=3,c=2$ and $a=9,b=6,c=4$ since those are the only ones that satisfy $3\mid(a+b+c+32)$ .
Having to finally choose from these two, we apply the divisibility rule for $7$ one last time to see that only $1216451004088320$ is divisible by $7$ , whereas $1216451004089640$ is not.
Therefore, $1216451004088320$ is the correct number which means that
$\overline{abc}=832$
which is in fact the correct solution of the problem.
Note: Another possible way is to simply divide the possible numbers with $3$ and/or $7$ and see the result. However, for purposes of proving this I added the divisibility rules of those two.
19! = 1 2 3 ... 18*19 Then, 19! ≡ 0 (mod 1000) and 19! ≡ 0 (mod 9) => 1+2+1+6+4+5+1+4+0+8+a+b+c+0+0+0 ≡ 0 (mod 9) 32+a+b+c ≡ 0 (mod 9) a+b+c ≡ 4 (mod 9)
If a ≡ n (mod x) and b ≡ m (mod x) Then a b ≡ m n (mod x)
19!/1000 ≡ 2 3 6 7 8 9 11 12 13 14 3 16 17 18 19 19!/1000 ≡ 2 3 6 7 8 9 1 2 3 4 3 6 7 8 9 ( mod 10) 19!/1000 ≡ (2^2) (3^3) 4 (6^2) (7^2) (8^2) (9^2) (mod 10) 19!/1000 ≡ 4 7 4 6 9 4 1 ≡ 8 4 6 ≡ 2 ≡ c (mod 10)
Then c=2 And: a+b+c ≡ a+ b +2 ≡ 4 (mod 9) a + b ≡ 2 ≡ 11 (mod 9)
Solutions (a,b) : (2,0),(0,2),(8,3),(3,8)
And (8,3) is the only solution
To solve this problem, you can do two (other way) ways below:
divide by 5 first (twice or three times if necessary), and then multiply by the quotient. Also, for every factor of 5 that you skip, be sure to also skip a factor of 2. You have to take the last 3 digits after every multiplication. So you would end up with something like this:
001 X 2 = 002 , 002 X 3 = 006 , 006 X 2 = 012 (drop a 2) , 012 X 1 = 012 (drop a 5) , 012 X 6 = 072 , 072 X 7 = 504 , 504 X 8 = 032 , 32 X 9 = 288 , 288 X 1 = 288 (drop a 2*5) , 288 X 11 = 168 , 168 X 12 = 016 , 016 X 13 = 208 , 208 X 7 = 456 (drop a 2) , 456 X 3 = 368 (drop a 5) , 368 X 16 = 888 , 888 X 17 = 096 , 096 X 18 = 728 , 728 X 19 = 832
For this problem, one can easily code this. I used python to code this problem. Using this code:
number=input("Enter a nonnegative integer to take the factorial of:")
product=1 for i in range(number): product = product*(i+1)
print(product)
I found out what "abc" was and you get that "abc" is 832.
This is a number theory problem, not a computing problem. If you use a computer to do it, might as well type it into WolframAlpha. Just use modular arithmetic to solve it. 19! / 1000 mod 1000 You take the 2, the 5, the 10, and the 15. Turn the 15 into 3*5, so you have {3,3,4,6,7,8,9,11,12,13,14,16,17,18,19,1000}. Now its just a simple mod bash
Log in to reply
Is there perhaps some way of using the given information to provide a simpler, less tedious, solution?
Log in to reply
Well, its divisible by 9 and 11, so we've got those divisibility rules. It's divisible by 16, so c000 is divisible by 16.
Log in to reply
@Robert Barr – I was also thinking the same but used a computer. How did you do it robert?
Log in to reply
@Shaurya Gupta – It's very easy to calculate the prime decomposition of 19!. You will notice that it's divisible by 1.000 (2^3 * 5^3) as well... which makes the task much easier!
@Robert Barr – Note: Using 9 and 11 only allows us to determine the answer up to a multiple of 99. We have to ignore $2^3 \times 5^3$ which give the last 3 zeros. So using $2 , 9 , 11$ also only allows us to determine the answer up to a multiple of $198$ , which is not sufficient.
However, we can just add more primes. For example, we could $2 \times 3^2 \times 7 \times \times 11 > 1000$ , which determines $\overline{abc}$ uniquely. This was the approach I used, in part since the divisibility rule of 7 uses blocks of 3.
Another approach is to realize that $\frac{19!} { 10^3}$ is a multiple of $2^{10} = 1024$ (actually it is a multiple of $2^{13}$ .
A very elegant solution to this question would be similar to that posted by Michael Tang at the link here: Pin the tail on the factorial .
You can apply his solution to this question which is very similar to one that was posted just last week...
Here is the solution but applied to this question:
There are 3 factors of 5 and 16 factors of $2$ in $19!$ . $5^{3} * 2^{3} = 10^{3}$ , which accounts for the last 3 zeros behind the long string of digits. Hence, we get $2^{16-3} = 2^{13} \mid \overline{121645100408abc}$
We know that for a number to be divided by $2^{n}$ , its last $n$ digits must be a number that is divided by $2^{n}$ . In this case, the number formed by the last 13 digits, i.e. $\overline{1645100408abc}$ must be divisible by $2^{13} = 8192$ .
Note that $\overline{1645100408abc} =\overline{1645100408000} + \overline{abc}$
Therefore, $\overline{1645100408000} + \overline{abc} \equiv 7360 + \overline{abc} \equiv 0 \pmod {8192}$ . Hence, since $\overline{abc}$ is a $3$ digit number, we get $\overline{abc} = 8192 - 7360 = \boxed{832}$ .
Log in to reply
Great that you can think of a similar problem and adapt the solution. Keep it up!
I've taken the liberty of converting this comment into a solution.
How did you get the 7360 at the end?
Log in to reply
The mod function is used when we are interested in the remainder, instead of the quotient. For example $5 \equiv 2 \pmod{3}$ because when $5$ is divided by $3$ , it leaves a remainder of $2$ .
Similarly, $\overline {1645100408abc} \equiv 7360 \pmod{8192}$ . That is how I arrive at $7360$ :)
On a side note, I just want to clarify the motivations behind using the mod function in this case. This is because we know that a number is divisible by another if the remainder is $0$ . Since we are interested in the remainder only, it may be appropriate to use the mod function.
Log in to reply
@Happy Melodies – Thanks.
nice solution
What I did is: I first realized that 19! is a multiple of 3 and hence, all digits should add up to a multiple of 3. Thus, we have a+b+c = 1(mod3) or, a+b+c = 3k+1 where k is a natural number. Again, we apply the divisibility rule for 11 as 19! is divisible by 11. Hence we approach the answer, trying out a few cases at the end.
Problem Loading...
Note Loading...
Set Loading...
A very elegant solution to this question would be similar to that posted by Michael Tang at the link here: Pin the tail on the factorial .
You can apply his solution to this question which is very similar to one that was posted just last week...
Here is the solution but applied to this question:
There are 3 factors of 5 and 16 factors of $2$ in $19!$ . $5^{3} * 2^{3} = 10^{3}$ , which accounts for the last 3 zeros behind the long string of digits. Hence, we get $2^{16-3} = 2^{13} \mid \overline{121645100408abc}$
We know that for a number to be divided by $2^{n}$ , its last $n$ digits must be a number that is divided by $2^{n}$ . In this case, the number formed by the last 13 digits, i.e. $\overline{1645100408abc}$ must be divisible by $2^{13} = 8192$ .
Note that $\overline{1645100408abc} =\overline{1645100408000} + \overline{abc}$
Therefore, $\overline{1645100408000} + \overline{abc} \equiv 7360 + \overline{abc} \equiv 0 \pmod {8192}$ . Hence, since $\overline{abc}$ is a $3$ digit number, we get $\overline{abc} = 8192 - 7360 = \boxed{832}$ .
The mod function is used when we are interested in the remainder, instead of the quotient. For example $5 \equiv 2 \pmod{3}$ because when $5$ is divided by $3$ , it leaves a remainder of $2$ .
Similarly, $\overline {1645100408abc} \equiv 7360 \pmod{8192}$ . That is how I arrive at $7360$ :)
On a side note, I just want to clarify the motivations behind using the mod function in this case. This is because we know that a number is divisible by another if the remainder is $0$ . Since we are interested in the remainder only, it may be appropriate to use the mod function.