Waste less time on Facebook — follow Brilliant.
×

\(90!\)

Can someone tell me how to do this problem: find the last 3 nonzero digits of \(90!\) I don't want the answer, just the method.

( ! Means factorial)

Note by William Isoroku
2 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Write it as product of prime factors raised to respective powers. You can start by removing all the powers of \(5\) and the same number of \(2\)s from the product as when multiplied, they don't change the last digits because they just add zeroes to the end. Now find the remainder when this number is divided by \(1000\). Yes, you have to use modular arithmetic, and no, it's not going to be easy. Raghav Vaidyanathan · 2 years, 3 months ago

Log in to reply

How do you do it with modular arithmetic? William Isoroku · 2 years, 3 months ago

Log in to reply

maybe through prime factorisation of 90! ? Andrea Palma · 2 years, 3 months ago

Log in to reply

@Andrea Palma No, Modular arthritic Rajdeep Dhingra · 2 years, 3 months ago

Log in to reply

@Rajdeep Dhingra Yes but I really think it should be faster to go mod 1000 after you have grouped as many same factor as possible, and in any way you must eliminate form the counting max power of 5 that divides 90! and the same power of 2. Andrea Palma · 2 years, 3 months ago

Log in to reply

@Andrea Palma yes, You are right. But factorizing 90! is not easy. Rajdeep Dhingra · 2 years, 3 months ago

Log in to reply

@Rajdeep Dhingra I completely agree with you. It's a pretty long work. Using a calculator I think this method should be faster:

start multiplying 1x2x3x4x5x6x7x8x9

when on the calculator appears a large number shorthen it by the following operations

1) if there are zero's at the last digits, then divide the number by 10^(number of zeros) 2) go mod 1000 (take as new number the last 3 digit)

and then keep multiplying as factorial requires

number x 10x11x12x13x14x14 and so on

This could be an algorithm

f:=1 for i= 2 to 90 do f:=f*i if f has many digits OR i = 90 do 1) f: = f cleared from all the last zeros 2) f:= last 3 digit of f; output f. Andrea Palma · 2 years, 3 months ago

Log in to reply

@Andrea Palma Here is a manual factorization of 90!. Don't bother looking at the funny calculations, just go to the bottom line. I didn't double checked the result. Hope I didn't miss anything!


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 6466 68 70 72 74 76 78 80 82 84 86 88 90


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^45

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^45

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^45

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

2^22 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^67

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

1 3 5 7 9 11 13 15 17 19 21

2 4 6 8 10 12 14 16 18 20 22


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^67

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

1 3 5 7 9 11 13 15 17 19 21

2^11 1 2 3 4 5 6 7 8 9 10 11


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^78

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

1 3 5 7 9 11 13 15 17 19 21

1 3 5 7 9 11

2 4 6 8 10


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^78

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

1 3 5 7 9 11 13 15 17 19 21

1 3 5 7 9 11

2^8

3 5


1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

2^86

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45

1 3 5 7 9 11 13 15 17 19 21

1 3 5 7 9 11

3 5


3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89

2^86

3 9 15 21 27 33 39 45 5 7 11 13 17 19 23 25 29 31 35 37 41 43

3 9 15 21 5 7 11 13 17 19

3 9 5 7 11

3 5


3^15 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29

5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89

2^86

3^8 1 3 5 7 9 11 13 15

5 7 11 13 17 19 23 25 29 31 35 37 41 43

3^4 1 3 5 7

5 7 11 13 17 19

3^3 5 7 11

3

5


3^15

3 9 15 21 27

5 7 11 13 17 19 23 25 29

5 25 35 55 65 85

7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89

2^86

3^12 5 7 11 13 5

5 7 11 13 17 19 23 25 29 31 35 37 41 43

3^4 1 3 5 7

5 7 11 13 17 19

3^3 5 7 11

3

5


3^15 3^12 3^4 3^3 3
3^3 3^5 3

5 7 5 7 11 13 17 19 23 29 5^2 5^3 5^4 5^2 7 11 13 17 7 11 13

7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 7^2 7 11

2^86

5 7 11 13 17 19 23 25 29 31 35 37 41 43

5 7

5 7 11 13 17 19

5 7 11

5


2^86

3^44

5^21

7^5 7 11 7 11 7 11 13 7 11 13 17 7 11 13 17 19 7 11 13 17 19 23 29 7 11 13 17 19 23 29 31 37 41 43 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89


2^86

3^44

5^21

7^13

11^8

13^6

17^5

19^4

23^3

29^3

31^2

37^2 41^2 43^2

47 53 59 61 67 71 73 79 83 89


2^86 x 3^44 x 5^21 x 7^13 x 11^8 x 13^6 x 17^5 x 19^4 x 23^3 x 29^3 x 31^2 x 37^2 x 41^2 x 43^2 x x 47 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89


Andrea Palma · 2 years, 3 months ago

Log in to reply

@Andrea Palma 2^86 x 3^44 x 5^21 x 7^13 x 11^8 x 13^6 x 17^5 x 19^4 x 23^3 x 29^3 x 31^2 x 37^2 x 41^2 x 43^2 x x 47 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89

eliminating 0s at the end

2^65 x 3^44 x 7^13 x 11^8 x 13^6 x 17^5 x 19^4 x 23^3 x 29^3 x 31^2 x 37^2 x 41^2 x 43^2 x 47 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89

go mod 1000

2^10 = 1024 = 24 2^65 = 24^6 x 32 = 232

3^10 =59094 = 94 3^44 = 94^4 x 81 =576

7^13 = 407

11^8 = 881

13^6 = 809

17^5 = 857

19^4 = 321

23^3 = 167

29^3 = 389

31^2 = 961

37^2 = 369

41^2 = 681

43^2 = 849

47 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89 = 277

952 Andrea Palma · 2 years, 3 months ago

Log in to reply

@Andrea Palma Yes and now mod 1000 Rajdeep Dhingra · 2 years, 3 months ago

Log in to reply

Might be 000 cause in 90 factorial there is 10x90x80 which results in 72000 and any number nx72000 results with the last digit 0. Whatever may be n , the last digit is 0 Ajay Chandra · 2 years, 3 months ago

Log in to reply

@Ajay Chandra Look closely, the question is to find the last three non zero digits. The last three non zero digits in \(123456700000000\) are \(5,6,7\). Raghav Vaidyanathan · 2 years, 3 months ago

Log in to reply

@Raghav Vaidyanathan oh! im sorry i didnt exactly see the question Ajay Chandra · 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...