Project Euler - Problem 160

Question

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)

I've successfully tackled this question for the given examples, my function can correctly find f(9), f(10), etc. However it struggles with larger numbers, especially the number the problem asks for - f(10^12).

My current optimizations are as follows: I remove trailing zeros from the multiplier and the sum, and shorten the sum to 5 digits after each multiplication. The code in python is as follows:

def SFTR (n):
 sum, a = 1, 2
 while a < n+1:
  mul  = int(re.sub("0+$","",str(a)))
  sum *= mul
  sum  = int(re.sub("0+$","",str(sum))[-5:])
  a   += 1
 return sum 

Can anyone tell me why this function is scaling so largely, and why its taking so long. Also, if anyone could hint me in the correct direction to optimize my algorithm. (a name of the general topic will suffice) Thank you.

Update:

I have made some changes for optimization and it is significantly faster, but it is still not fast enough for f(10^12). Can anyone tell me whats making my code slow or how to make it faster?

def SFTR (n):
    sum, a = 1, 2
    while a < n+1:
        mul  = a

        while(mul % 10 == 0): mul = mul/10
        mul  = mul % 100000

        sum *= mul

        while(sum % 10 == 0): sum = sum/10
        sum  = sum % 100000

        a   += 1
    return sum

Answer 1

Building strings frequently is expensive. I'd rather use the modulo operator when truncating to the last five digits.

python -m timeit 'x = str(111111111111111111111111111111111)[-5:]'
1000000 loops, best of 3: 1.09 usec per loop
python -m timeit 'x = 111111111111111111111111111111111 % 100000'
1000000 loops, best of 3: 0.277 usec per loop

The same applies to stripping the trailing zeros. There should be a more efficient way to do this, and you probably don't have to do it in every single step.

I didn't check your algorithm for correctness, though, it's just a hint for optimization.

Answer 2

mul can get very big. Is that necessary? If I asked you to compute the last 5 non-zero digits of 1278348572934847283948561278387487189900038 * 38758 by hand, exactly how many digits of the first number do you actually need to know?

Answer 3

In fact, you might even note that there are only a restricted set of possible trailing non-zero digits. If I recall correctly, there are only a few thousand possible trailing non-zero digit combinations, when you look only at the last 5 digits. For example, is it possible for the final non-zero digit ever to be odd? (Ignore the special cases of 0! and 1! here.)