You are told that the last fourteen digits of 3 3 ! (from the right) are 9 4 4 0 1 a b c 0 0 0 0 0 0 , where a , b and c are digits. What is the value of a b c ?
Details and Assumptions:
a b c means 1 0 0 a + 1 0 b + 1 c , as opposed to a × b × c . As an explicit example, for a = 2 , b = 3 , c = 4 , a b c = 2 3 4 and not 2 × 3 × 4 = 2 4 .
The last 3 digits of the number 1 0 2 3 are 0 2 3 .
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.
Beautiful. Congrats, this is gorgeous.
This is definitely the most elegant solution here.
hey the solution looks good, but i don't know Legendre's Formula, so it would be nice if you could tell me what it is.
Log in to reply
Legendre's formula gives you a way to find the number of factors of a prime p in n ! . You're in luck - I in fact just wrote a little piece about it. Link: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=300&t=565636&p=3310038#p3310038.
This much elegant.
Brilliant solution.
smarter solution.nice use of 2^7=128.i could not see that...........
Great solution!
Thanks, everyone! :)
Can please explain a bit more about your last 6 lines?
Log in to reply
Which part specifically? The part beginning with "so 94401ab must be divisible by 128?"
Did ya divide 9440100 by 128 by long division to know the remainder 100?
The prime factorization of 3 3 ! is
2 3 1 ⋅ 3 1 5 ⋅ 5 7 ⋅ 7 4 ⋅ 1 1 3 ⋅ 1 3 2 ⋅ 1 7 ⋅ 1 9 ⋅ 2 3 ⋅ 2 9 ⋅ 3 1
Since it's return in base representation of 1 0 , so the last 7 digits of 3 3 ! are all 0 's. That's because 3 3 ! is written in base 1 0 representation and has a total of 7 factors of 5 as the largest prime factor of 1 0 is 5
Removing the last seven digits means the remaining 7 digits is 9 4 4 0 1 a b , thus c = 0
Because we're dividing 3 3 ! by 1 0 7 = 2 7 ⋅ 5 7 , we are left with
2 2 4 ⋅ 3 1 5 ⋅ 7 4 ⋅ 1 1 3 ⋅ 1 3 2 ⋅ 1 7 ⋅ 1 9 ⋅ 2 3 ⋅ 2 9 ⋅ 3 1
So we want to find the last two digits of the above expression: m o d 1 0 0
2 2 4 ≡ ( 2 4 ) 6 ≡ 1 6 6 ≡ 1 6
3 1 5 ≡ ( 3 5 ) 3 ≡ 4 3 3 ≡ 7
And apply the similar congruences to the rest of the terms, we have
≡ 1 6 ⋅ 7 ⋅ 1 ⋅ 3 1 ⋅ 6 9 ⋅ 1 7 ⋅ 1 9 ⋅ 2 3 ⋅ 2 9 ⋅ 3 1
≡ 2 8
So a = 2 , b = 8 . Hence, a b c = 2 8 0
However, it's a bit too tedious
Log in to reply
If you use legendre's function the prime factorization of n! can be found quite quickly.
it's a good method and understandable for me
Nice!
same approach!! :)
Same
Notice that the order of 5 in 3 3 ! is 7 because 5 , 1 0 , 1 5 , 2 0 , 3 0 each contribute one factor and 2 5 contributes two. Therefore the number ends in 7 zeros (the order of 2 being much bigger than that of 5 ), so c = 0 .
To determine the remaining digits, we will generalize the familiar rule that the number is divisible by four precisely when its last two digits are divisible by four.
Lemma 2 n divides last n digits of A if and only if 2 n divides A .
Proof Write A = B ⋅ 1 0 n + C . This means that A ≡ C ( m o d 2 n ) and the lemma follows.
As there are many factors of 2 in 3 3 ! (certainly more than 1 6 ) and we only used 7 of them for the last 7 zeros, it's clear that 2 7 = 1 2 8 divides 3 3 ! . The lemma then says that also 9 4 4 0 1 a b is divisible by 1 2 8 . So it's enough to divide 9 4 4 0 1 9 9 by 1 2 8 to get 9 4 4 0 1 9 9 = 1 2 8 ⋅ 7 3 7 5 1 + 7 1 . This means that the number we are looking for is 9 4 4 0 1 2 8 and consequently the answer is a b c = 2 8 0 .
Perhaps it will be useful to also give a little bit of motivation. Well, after a few unsuccesful attemps of computing 3 3 ! / 1 0 7 ( m o d 1 0 0 ) directly, I stopped to think how might the digits at the front help us find the answer. I knew the answer was divisible by four and that told me that the last two digits are divisible by four as well, so that already narrows down the possible choices to 1 0 0 , … , 1 9 6 . But why not use the divisibility by 8 instead? That reduces the choices further to 1 0 4 , … , 1 9 2 . And then I realized that the pattern continues and we can go all the way up to 1 2 8 which is big enough to leave us with precisely one choice that must be the answer.
Log in to reply
yup.i tried that.but there is a 168 too.hoe to eliminate that??
It's possible to compute 3 3 ! / 1 0 7 directly by first getting the prime factorization of 33! using legendre's function, and then dividing by 1 0 7 . Then evaluate the remaining number's modulo 100 residue, which is easy.
Log in to reply
Well, sure, but by being I unsuccessful I didn't mean that I don't know how to compute it if need be. I meant that I didn't find an elegant non-brute-force approach. I certainly don't want to be looking at the prime factorization when there is a nice way of avoiding it (like here).
My solution was a lot like yours. (I'm surprised that most others used a brute-force method.)
Log in to reply
It's not very much brute force , and probably faster than searching about for Marek's lemma if you didn't already have an inkling that something like that might exist. (I figured we'd used up all the factors of 5 already so there wasn't going to be any way to relate the other factors of 2 to base 10).
Log in to reply
Indeed, it's probably faster to compute the prime factorization and multiply everything out. Even better, just enter 33! into any reasonable calculator and see what the result is :)
On the other hand, I agree that the 2 n rule isn't obvious if you don't already know it (even though it's obvious generalization of the 2/4/8 rules everybody's familiar with).
On the third hand, there are great many rules for division in any base, and even proving the familiar 2/3/4/5/6/8/9/11 rules in base 10 is quite amusing if you haven't done it before :)
First I made a prime factorization of 33!
33! = 3 1 × 2 9 × 2 3 × 1 9 × 1 7 × 1 3 2 × 1 1 3 × 7 4 × 5 7 × 3 1 5 × 2 3 1
Knowing that the last 6 digits of the 33! is zero, so I eliminated all those zeroes by removing 2 6 × 5 6 = 1 0 6 to make our last 3 digits be a b c
Now the reduced prime factorization :
3 1 × 2 9 × 2 3 × 1 9 × 1 7 × 1 3 2 × 1 1 3 × 7 4 × 5 × 3 1 5 × 2 2 5
since 2 × 5 = 10. We can easily say that our last digit c = 0. Again we remove 2 × 5 to make our last 3 digits be 1 a b . :
3 1 × 2 9 × 2 3 × 1 9 × 1 7 × 1 3 2 × 1 1 3 × 7 4 × 3 1 5 × 2 2 4
In solving for digit b , I multiplied all the last digits in the prime factorization (eg . 2 2 4 = 6):
1 × 9 × 3 × 9 × 7 × 9 × 1 × 1 × 7 × 6 = 642, 978
So it means our digit b is equal to 8.
Lastly in solving digit a , I use the divibility rules of 8. Since our last 3 digit number should be 1 a 8. The only possible values of digit a to make 1 a 8 be a divisible of 8 is 2 and 6. So I divided each by 8.
8 1 2 8 = 16 8 1 6 8 = 21
Clearly from this, digit a is must be 2, since 8 is equal to 2 3 and we if we try to eliminate 2 3 from 2 2 4 there would be still 2 2 1 which makes the last 3 digit still an even number.
So, a b c = 2 8 0
In your solution, I could not understand the last part:
Clearly from this, digit a is must be 2, since 8 is equal to 2 3 and we if we try to eliminate 2 3 from 2 2 4 there would be still 2 2 1 which makes the last 3 digit still an even number.
What does it mean?
Log in to reply
Okay. So from 33! which is equal to 3 1 × 2 9 × 2 3 × 1 9 × 1 7 × 1 3 2 × 1 1 3 × 7 4 × 5 7 × 3 1 5 × 2 3 1 ... we reduced it into 3 1 × 2 9 × 2 3 × 1 9 × 1 7 × 1 3 2 × 1 1 3 × 7 4 × 3 1 5 × 2 2 4 to eliminate all the last zero digits. Thus c = 0
So now, our last last digits would be in the form of 9 4 4 0 1 a 8 ... since b = 8. Knowing that 2 2 4 contains 8, it means that our last three digits must be a divible of 8. so a could be either 2 or 6. So the two numbers are 128 and 168.
To confirm what really is the value of a . We could divide each number by 2 until one of it ends with an odd number. So
XXXXX128 / 2 = XXXXX64 / 2 = XXXXX32 / 2 = XXXXX16
XXXXX168 / 2 = XXXXX84 / 2 = XXXXX42 / 2 = XXXXX21
"XXXXX" represents the preceding digits of the number.
From this we can conlude that the number must end in 128 to divide all the others 2's remaining from 2 2 4 .
Log in to reply
Okay, now I get it.
Log in to reply
@Akshat Jain – 78987128 be the first xxxxx128.and we are not getting that
Log in to reply
@Bumba Biswas – I put XXXXX128, so that XXXXXX must denote ALL the other numbers that precede 128.
In your case, you count my X's which is eventually 5 x's and put the first 5 digits that precede 128.
For example, in this number : 162532163516351263567128
I would eventually denote it as XXXXX128 instead of putting XXXXXXXXXXXXXXXXXXXXX128.
78987128 be the first xxxxx128.and we are not getting that
Put it in the calculator... 33! = 8683317618811886495518194401280000000. Thus, abc = 280.
You wont be able to learn anything
There are five multiples of 5 and one multiple of 25 in 33!. Therefore, there are 7 zeros at the end. c=0.
Then, we observe that 9440000 is divisible by 128. Therefore, in order to make 94401ab divisible by 128. ab=28.
I typed 33X32X31X...X3X2X1 into my powerful calculator and it gave me the answer!
Main Idea : Convert the factorial as a product of primes.
The primes before 3 1 are : 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 3 1 , 3 3
The highest power of a prime p contained in a factorial is given by:
⌊ p n ⌋ + ⌊ p 2 n ⌋ + . . . + ⌊ p k n ⌋ , p k ≤ n
Keeping the above facts in find we write: 3 3 ! = 2 3 1 ⋅ 3 1 6 ⋅ 5 7 ⋅ 7 4 ⋅ 1 1 3 ⋅ 1 3 2 ⋅ 1 7 ⋅ 1 9 ⋅ 2 3 ⋅ 2 9 ⋅ 3 1 3 3 ! = 1 0 7 ( 2 2 4 ⋅ 3 1 5 ⋅ 7 4 ⋅ 1 1 3 ⋅ 1 3 2 ⋅ 1 7 ⋅ 1 9 ⋅ 2 3 ⋅ 2 9 ⋅ 3 1 ) = 1 0 7 ⋅ t Observe that the last 7 digits of 3 3 ! are 0 so c = 0 .
Work t ( m o d 1 0 0 ) to retrieve the 8 th and 9 th digit of 3 3 ! .
Clearly, t ≡ 0 ( m o d 4 )
The only obstacle left is to work t ( m o d 2 5 )
2 2 4 ≡ 1 0 2 4 2 ⋅ 2 4 ≡ 1 6 ( m o d 2 5 ) 3 1 5 ≡ 2 7 5 ≡ 2 5 ≡ 7 ( m o d 2 5 ) 7 4 ≡ 1 ( m o d 2 5 ) 1 1 3 ≡ 1 1 ⋅ − 4 ≡ 6 ( m o d 2 5 ) 1 3 2 ≡ − 6 ( m o d 2 5 ) 1 7 ⋅ 1 9 ≡ − 8 ⋅ − 6 ≡ − 2 ( m o d 2 5 ) 2 3 ⋅ 2 9 ⋅ 3 1 ≡ − 2 ⋅ 4 ⋅ 6 ≡ 2 ( m o d 2 5 )
Now multiply all the above congruences to get:
t ≡ 1 6 ⋅ 7 ⋅ 1 ⋅ 6 ⋅ ( − 6 ) ⋅ ( − 2 ) ⋅ 2 ≡ 1 6 ⋅ 7 ⋅ 6 ⋅ 2 4 ≡ 1 6 ⋅ 6 ⋅ 7 ⋅ ( − 1 ) ≡ ( − 4 ) ⋅ ( − 7 ) ≡ 3 ( m o d 2 5 )
By the Chinese Remainder Theorem, t ≡ 2 8 ( m o d 1 0 0 )
So a = 2 , b = 8 , c = 0
Answer : a b c = 2 8 0
Using wolfram alpha:
1 |
|
Problem Loading...
Note Loading...
Set Loading...
By Legendre's Formula, there are
⌊ 5 3 3 ⌋ + ⌊ 2 5 3 3 ⌋ = 7
factors of 5 in 3 3 ! , and there are
⌊ 2 3 3 ⌋ + ⌊ 4 3 3 ⌋ + ⌊ 8 3 3 ⌋ + ⌊ 1 6 3 3 ⌋ + ⌊ 3 2 3 3 ⌋ = 3 1
factors of 2 in 3 3 ! . So, there are exactly 7 factors of 1 0 in 3 3 ! . Since the expression currently ends with 6 zeroes, we must have c = 0 .
If there are 3 1 factors of 2 in 3 3 ! , we also know that 2 1 4 ∣ 3 3 ! . Since a positive integer is divisible by 2 1 4 if and only if its last 1 4 digits are divisible by 2 1 4 ,
2 1 4 9 4 4 0 1 a b 0 0 0 0 0 0 0
must be an integer. To simplify this fraction, we can write
2 1 4 9 4 4 0 1 a b 0 0 0 0 0 0 0 = 2 1 4 1 0 7 ⋅ 9 4 4 0 1 a b = 2 7 5 7 ⋅ 9 4 4 0 1 a b .
This means that 9 4 4 0 1 a b must be divisible by 2 7 = 1 2 8 . Using long division, we can find that 9 4 4 0 1 a b = 9 4 4 0 1 0 0 + a b ≡ 1 0 0 + a b ( m o d 1 2 8 ) , so a b ≡ 2 8 ( m o d 1 2 8 ) . Because a b is a two-digit number, we must have a b = 2 8 .
In conclusion, a b c = 2 8 0 .