Pin the tail on the factorial

You are told that the last fourteen digits of 33 ! 33! (from the right) are 94401 a b c 000000 , \overline{94401abc000000}, where a , b a, b and c c are digits. What is the value of a b c \overline{abc} ?

Details and Assumptions:

  • a b c \overline{abc} means 100 a + 10 b + 1 c 100a + 10b + 1c , as opposed to a × b × c a \times b \times c . As an explicit example, for a = 2 , b = 3 , c = 4 a=2, b=3, c=4 , a b c = 234 \overline{abc} = 234 and not 2 × 3 × 4 = 24 2 \times 3 \times 4 = 24 .

  • The last 3 digits of the number 1023 1023 are 023 023 .


The answer is 280.

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.

8 solutions

Michael Tang
Nov 25, 2013

By Legendre's Formula, there are

33 5 + 33 25 = 7 \left\lfloor\frac{33}{5}\right\rfloor + \left\lfloor\frac{33}{25}\right\rfloor = 7

factors of 5 5 in 33 ! , 33!, and there are

33 2 + 33 4 + 33 8 + 33 16 + 33 32 = 31 \left\lfloor\frac{33}{2}\right\rfloor + \left\lfloor\frac{33}{4}\right\rfloor + \left\lfloor\frac{33}{8}\right\rfloor + \left\lfloor\frac{33}{16}\right\rfloor + \left\lfloor\frac{33}{32}\right\rfloor = 31

factors of 2 2 in 33 ! . 33!. So, there are exactly 7 7 factors of 10 10 in 33 ! . 33!. Since the expression currently ends with 6 6 zeroes, we must have c = 0. c = 0.

If there are 31 31 factors of 2 2 in 33 ! , 33!, we also know that 2 14 33 ! . 2^{14} \mid 33!. Since a positive integer is divisible by 2 14 2^{14} if and only if its last 14 14 digits are divisible by 2 14 , 2^{14},

94401 a b 0000000 2 14 \dfrac{\overline{94401ab0000000}}{2^{14}}

must be an integer. To simplify this fraction, we can write

94401 a b 0000000 2 14 = 1 0 7 94401 a b 2 14 = 5 7 94401 a b 2 7 . \dfrac{\overline{94401ab0000000}}{2^{14}} = \dfrac{10^7 \cdot \overline{94401ab}}{2^{14}} = \dfrac{5^7 \cdot \overline{94401ab}}{2^7}.

This means that 94401 a b \overline{94401ab} must be divisible by 2 7 = 128. 2^7 = 128. Using long division, we can find that 94401 a b = 9440100 + a b 100 + a b ( m o d 128 ) , \overline{94401ab} = 9440100 + \overline{ab} \equiv 100 + \overline{ab} \pmod{128}, so a b 28 ( m o d 128 ) . \overline{ab} \equiv 28 \pmod{128}. Because a b \overline{ab} is a two-digit number, we must have a b = 28. \overline{ab} = 28.

In conclusion, a b c = 280 . \overline{abc} = \boxed{280}.

Beautiful. Congrats, this is gorgeous.

Guillermo Angeris - 7 years, 6 months ago

This is definitely the most elegant solution here.

Sean Elliott - 7 years, 6 months ago

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.

Ghanashyam Chakravarthi - 7 years, 6 months ago

Log in to reply

Legendre's formula gives you a way to find the number of factors of a prime p p in n ! . 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.

Michael Tang - 7 years, 6 months ago

This much elegant.

Mehedi Hasan - 7 years, 6 months ago

Brilliant solution.

Zawad Chowdhury - 7 years, 6 months ago

smarter solution.nice use of 2^7=128.i could not see that...........

Bumba Biswas - 7 years, 6 months ago

Great solution!

Josh Kolenbrander - 7 years, 6 months ago

Thanks, everyone! :)

Michael Tang - 7 years, 6 months ago

Can please explain a bit more about your last 6 lines?

Krystal D'Souza - 7 years, 6 months ago

Log in to reply

Which part specifically? The part beginning with "so 94401ab must be divisible by 128?"

Michael Tang - 7 years, 6 months ago

Did ya divide 9440100 by 128 by long division to know the remainder 100?

Led Tasso - 7 years, 6 months ago

Log in to reply

Yes. That's what I did.

Michael Tang - 7 years, 6 months ago
Pi Han Goh
Nov 24, 2013

The prime factorization of 33 ! 33! is

2 31 3 15 5 7 7 4 1 1 3 1 3 2 17 19 23 29 31 2^{31} \cdot 3^{15} \cdot 5^{7} \cdot 7^4 \cdot 11^3 \cdot 13^2 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31

Since it's return in base representation of 10 10 , so the last 7 7 digits of 33 ! 33! are all 0 0 's. That's because 33 ! 33! is written in base 10 10 representation and has a total of 7 7 factors of 5 5 as the largest prime factor of 10 10 is 5 5

Removing the last seven digits means the remaining 7 digits is 94401 a b \overline{94401ab} , thus c = 0 c=0

Because we're dividing 33 ! 33! by 1 0 7 = 2 7 5 7 10^7 = 2^7 \cdot 5^7 , we are left with

2 24 3 15 7 4 1 1 3 1 3 2 17 19 23 29 31 2^{24} \cdot 3^{15} \cdot 7^4 \cdot 11^3 \cdot 13^2 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31

So we want to find the last two digits of the above expression: m o d 100 \bmod{100}

2 24 ( 2 4 ) 6 1 6 6 16 2^{24} \equiv (2^4)^6 \equiv 16^6 \equiv 16

3 15 ( 3 5 ) 3 4 3 3 7 3^{15} \equiv (3^5)^3 \equiv 43^3 \equiv 7

And apply the similar congruences to the rest of the terms, we have

16 7 1 31 69 17 19 23 29 31 \equiv 16 \cdot 7 \cdot 1 \cdot 31 \cdot 69 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31

28 \equiv 28

So a = 2 , b = 8 a=2, b=8 . Hence, a b c = 280 \overline{abc} = \boxed{280}

However, it's a bit too tedious

Gari Chua - 7 years, 6 months ago

Log in to reply

If you use legendre's function the prime factorization of n! can be found quite quickly.

Arkan Megraoui - 7 years, 6 months ago

it's a good method and understandable for me

Subhadeep Biswas - 7 years, 6 months ago

Nice!

Edward Jiang - 7 years, 6 months ago

same approach!! :)

Aman Sinha - 7 years, 6 months ago

Same

Gari Chua - 7 years, 6 months ago
Marek Bernat
Nov 25, 2013

Notice that the order of 5 5 in 33 ! 33! is 7 7 because 5 , 10 , 15 , 20 , 30 5, 10, 15, 20, 30 each contribute one factor and 25 25 contributes two. Therefore the number ends in 7 7 zeros (the order of 2 2 being much bigger than that of 5 5 ), so c = 0 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 2^n divides last n n digits of A A if and only if 2 n 2^n divides A A .

Proof Write A = B 1 0 n + C A = B \cdot 10^n + C . This means that A C ( m o d 2 n ) A \equiv C \pmod{2^n} and the lemma follows.

As there are many factors of 2 2 in 33 ! 33! (certainly more than 16 16 ) and we only used 7 7 of them for the last 7 7 zeros, it's clear that 2 7 = 128 2^7 = 128 divides 33 ! 33! . The lemma then says that also 94401 a b \overline {94401ab} is divisible by 128 128 . So it's enough to divide 9440199 9440199 by 128 128 to get 9440199 = 128 73751 + 71 9440199 = 128 \cdot 73751 + 71 . This means that the number we are looking for is 9440128 9440128 and consequently the answer is a b c = 280 \overline {abc} = 280 .

Perhaps it will be useful to also give a little bit of motivation. Well, after a few unsuccesful attemps of computing 33 ! / 1 0 7 ( m o d 100 ) 33! / 10^7 \pmod{100} 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 100 , , 196 100, \dots, 196 . But why not use the divisibility by 8 8 instead? That reduces the choices further to 104 , , 192 104 , \dots, 192 . And then I realized that the pattern continues and we can go all the way up to 128 128 which is big enough to leave us with precisely one choice that must be the answer.

Marek Bernat - 7 years, 6 months ago

Log in to reply

yup.i tried that.but there is a 168 too.hoe to eliminate that??

Bumba Biswas - 7 years, 6 months ago

It's possible to compute 33 ! / 1 0 7 33!/10^7 directly by first getting the prime factorization of 33! using legendre's function, and then dividing by 1 0 7 10^7 . Then evaluate the remaining number's modulo 100 residue, which is easy.

Arkan Megraoui - 7 years, 6 months ago

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).

Marek Bernat - 7 years, 6 months ago

Log in to reply

@Marek Bernat Yes your method is neat :-D

Arkan Megraoui - 7 years, 6 months ago

My solution was a lot like yours. (I'm surprised that most others used a brute-force method.)

Peter Byers - 7 years, 6 months ago

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).

Matt McNabb - 7 years, 6 months ago

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 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 :)

Marek Bernat - 7 years, 6 months ago

First I made a prime factorization of 33!

33! = 31 × 29 × 23 × 19 × 17 × 1 3 2 × 1 1 3 × 7 4 × 5 7 × 3 15 × 2 31 31 \times 29 \times 23 \times 19 \times 17 \times 13^{2} \times 11^{3} \times 7^{4} \times 5^{7} \times 3^{15} \times 2^{31}

Knowing that the last 6 digits of the 33! is zero, so I eliminated all those zeroes by removing 2 6 × 5 6 2^{6} \times 5^{6} = 1 0 6 10^{6} to make our last 3 digits be a b c \overline{abc}

Now the reduced prime factorization :

31 × 29 × 23 × 19 × 17 × 1 3 2 × 1 1 3 × 7 4 × 5 × 3 15 × 2 25 31 \times 29 \times 23 \times 19 \times 17 \times 13^{2} \times 11^{3} \times 7^{4} \times 5 \times 3^{15} \times 2^{25}

since 2 × 5 2 \times 5 = 10. We can easily say that our last digit c \overline{c} = 0. Again we remove 2 × 5 2 \times 5 to make our last 3 digits be 1 a b \overline{ab} . :

31 × 29 × 23 × 19 × 17 × 1 3 2 × 1 1 3 × 7 4 × 3 15 × 2 24 31 \times 29 \times 23 \times 19 \times 17 \times 13^{2} \times 11^{3} \times 7^{4} \times 3^{15} \times 2^{24}

In solving for digit b \overline{b} , I multiplied all the last digits in the prime factorization (eg . 2 24 2^{24} = 6):

1 × 9 × 3 × 9 × 7 × 9 × 1 × 1 × 7 × 6 1 \times 9 \times 3 \times 9 \times 7 \times 9 \times 1 \times 1 \times 7 \times 6 = 642, 978

So it means our digit b \overline{b} is equal to 8.

Lastly in solving digit a \overline{a} , I use the divibility rules of 8. Since our last 3 digit number should be 1 a \overline{a} 8. The only possible values of digit a \overline{a} to make 1 a \overline{a} 8 be a divisible of 8 is 2 and 6. So I divided each by 8.

128 8 \frac{128}{8} = 16 168 8 \frac{168}{8} = 21

Clearly from this, digit a \overline{a} is must be 2, since 8 is equal to 2 3 2^{3} and we if we try to eliminate 2 3 2^{3} from 2 24 2^{24} there would be still 2 21 2^{21} which makes the last 3 digit still an even number.

So, a b c \overline{abc} = 280 \boxed{280}

In your solution, I could not understand the last part:

Clearly from this, digit a \overline{a} is must be 2, since 8 is equal to 2 3 2^3 and we if we try to eliminate 2 3 2^3 from 2 24 2^{24} there would be still 2 21 2^{21} which makes the last 3 digit still an even number.

What does it mean?

Akshat Jain - 7 years, 6 months ago

Log in to reply

Okay. So from 33! which is equal to 31 × 29 × 23 × 19 × 17 × 1 3 2 × 1 1 3 × 7 4 × 5 7 × 3 15 × 2 31 31\times 29 \times 23 \times 19 \times 17 \times 13^{2} \times 11^{3} \times 7^{4} \times 5^{7} \times 3^{15} \times 2^{31} ... we reduced it into 31 × 29 × 23 × 19 × 17 × 1 3 2 × 1 1 3 × 7 4 × 3 15 × 2 24 31\times 29 \times 23 \times 19 \times 17 \times 13^{2} \times 11^{3} \times 7^{4} \times 3^{15} \times 2^{24} to eliminate all the last zero digits. Thus c \overline{c} = 0

So now, our last last digits would be in the form of 94401 a 8 \overline {94401a8} ... since b \overline{b} = 8. Knowing that 2 24 2^{24} contains 8, it means that our last three digits must be a divible of 8. so a \overline{a} could be either 2 or 6. So the two numbers are 128 and 168.

To confirm what really is the value of a \overline{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 24 2^{24} .

Rey Francis Famulagan - 7 years, 6 months ago

Log in to reply

Okay, now I get it.

Akshat Jain - 7 years, 6 months ago

Log in to reply

@Akshat Jain 78987128 be the first xxxxx128.and we are not getting that

Bumba Biswas - 7 years, 6 months ago

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.

Rey Francis Famulagan - 7 years, 6 months ago

78987128 be the first xxxxx128.and we are not getting that

Bumba Biswas - 7 years, 6 months ago
Manan Dadhania
Nov 30, 2013

Put it in the calculator... 33! = 8683317618811886495518194401280000000. Thus, abc = 280.

You wont be able to learn anything

Sagnik Das - 7 years, 6 months ago
Dickson Chan
Nov 26, 2013

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!

bobby jim - 7 years, 6 months ago
Aditya Parson
Nov 25, 2013

Main Idea : Convert the factorial as a product of primes.

The primes before 31 31 are : 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 33 2,3,5,7,11,13,17,19,23,29,31,33

The highest power of a prime p p contained in a factorial is given by:

n p + n p 2 + . . . + n p k , p k n \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor+ ... + \lfloor \frac{n}{p^k} \rfloor , \ \ p^k \leq n

Keeping the above facts in find we write: 33 ! = 2 31 3 16 5 7 7 4 1 1 3 1 3 2 17 19 23 29 31 \ \ 33!=2^{31} \cdot 3^{16} \cdot 5^{7} \cdot 7^{4} \cdot 11^{3} \cdot 13^2 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 33 ! = 1 0 7 ( 2 24 3 15 7 4 1 1 3 1 3 2 17 19 23 29 31 ) = 1 0 7 t \\33!=10^7(2^{24}\cdot 3^{15} \cdot 7^{4} \cdot 11^{3} \cdot 13^2 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31)=10^7 \cdot t Observe that the last 7 7 digits of 33 ! 33! are 0 0 so c = 0 c=0 .

Work t ( m o d 100 ) t \pmod {100} to retrieve the 8 8 th and 9 9 th digit of 33 ! 33! .

Clearly, t 0 ( m o d 4 ) t \equiv 0 \pmod{4}

The only obstacle left is to work t ( m o d 25 ) t \pmod{25}

2 24 102 4 2 2 4 16 ( m o d 25 ) 2^{24} \equiv 1024^2 \cdot 2^4 \equiv 16 \pmod{25} 3 1 5 2 7 5 2 5 7 ( m o d 25 ) \\ 3^15 \equiv 27^5 \equiv 2^5 \equiv 7 \pmod{25} 7 4 1 ( m o d 25 ) \\ 7^4 \equiv 1 \pmod{25} 1 1 3 11 4 6 ( m o d 25 ) \\ 11^3 \equiv 11 \cdot -4 \equiv 6 \pmod{25} 1 3 2 6 ( m o d 25 ) \\ 13^2 \equiv -6 \pmod{25} 17 19 8 6 2 ( m o d 25 ) \\17 \cdot 19 \equiv -8 \cdot -6 \equiv -2 \pmod{25} 23 29 31 2 4 6 2 ( m o d 25 ) \\23 \cdot 29 \cdot 31 \equiv -2 \cdot 4 \cdot 6 \equiv 2 \pmod{25}

Now multiply all the above congruences to get:

t 16 7 1 6 ( 6 ) ( 2 ) 2 16 7 6 24 16 6 7 ( 1 ) ( 4 ) ( 7 ) 3 ( m o d 25 ) t \equiv 16 \cdot 7 \cdot 1 \cdot 6 \cdot(-6) \cdot (-2) \cdot 2 \equiv 16 \cdot 7 \cdot 6 \cdot 24 \equiv 16\cdot 6 \cdot 7 \cdot (-1) \equiv (-4) \cdot (-7)\equiv 3 \pmod{25}

By the Chinese Remainder Theorem, t 28 ( m o d 100 ) t \equiv 28 \pmod{100}

So a = 2 , b = 8 , c = 0 a=2, b=8, c=0

Answer : a b c = 280 \\ \overline{abc}=\boxed{280}

Formatting error:

3 1 5 3^15 should be 3 15 3^{15} .

Aditya Parson - 7 years, 6 months ago
Nam Diện Lĩnh
Jun 19, 2015

Using wolfram alpha:

1
33! mod 10^14

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...