Can someone tell me how to do this problem: find the last 3 nonzero digits of I don't want the answer, just the method.
( ! Means factorial)
Note by
William Isoroku
6 years, 2 months ago
No vote yet
1 vote
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
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 2s 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.
maybe through prime factorisation of 90! ?
Log in to reply
No, Modular arthritic
Log in to reply
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.
Log in to reply
yes, You are right. But factorizing 90! is not easy.
Log in to reply
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.
Log in to reply
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
Log in to reply
Yes and now mod 1000
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
How do you do it with modular arithmetic?
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
Log in to reply
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.
Log in to reply
oh! im sorry i didnt exactly see the question