My Blog List

Tuesday, July 19, 2016

Project Euler 160 Factorial trailing digits

It took about 8days from start to solving this problem (last non-zero digits of factorial)
First time I searched 0 to 1000000000000.
I doubt that my computer compute this logig in my life?
and searching how to find last zeros count of N factorial

finally I made condition

ex) 10! = 1 * 2* 3* 4 * 5* 6* 7 * 8 *9 *10

2*5 make 0 digit

so we should find multiple of 5
5, 10 that is all

5 = 5*1
10 = 5*2

10! = 5^2 * 2! * (10a +1) (10a +2)  (10a +3) (10a +4) (10a +6).. (10a +9) mod m
10! = 10^2 * 2! * (10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9)..

what if 100! and m is 10 ???

100! = 10^20 * 20! *  ((10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9))^10

so we can use this and solve 1000000000000 ! mod 100000






https://projecteuler.net/problem=160

For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,
9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664
Find f(1,000,000,000,000)

No comments:

Post a Comment