Zeroes After a Factorial

This is something like "Maths+Programming".

See that number of zeroes at end of $n!$ in base $k$ will be same as the maximum exponent of $k$ in $n!$ .

Hence, finding maximum power of $k$ that divides $n!$ will give us $f(n,k)$ .

1
2
3
4
5
6
7

import math
def f(n,k):
    li=[]
    for i in range(int(math.log(math.factorial(n),k))):
        if math.factorial(n)%k**i==0:
            li.append(i)
    return max(li)

By asking $max(li)$ in this program, we get maximum power of $k$ that divides $n!$ .

Now this is for $g(r)$

1
2
3
4
5

def g(r):
    k=0
    for i in range(2,r+1):
        k+=f(r,i)
    return k

This returns $g(100) = \boxed{1299}$ , in a very short time...

The following is Aditya's solution, just translated to haskell:

1
2
3
4
5
6
7
8

factorial n = product [1..n]

f :: Integer -> Integer -> Integer
f n k
    | (n `mod` k == 0) = 1 + (f (quot n k) k)
    | otherwise = 0

g r = sum $ map (\x -> (f (factorial r) x)) [2..r]

MATLAB Code : :

   function y=factzero_inbase(n,k)
   f = factor(k);
   fu = unique(f);
   i=1;
   while i<=length(fu)
      z(i)=0;
     j=fu(i);
     while j<=n
         z(i)=z(i)+fix(n/j);
          j=j*fu(i);
      end
      z(i)=fix(z(i)/length(find(f==fu(i))));
     i=i+1;
   end
    y = min(z);
   end

This is very easy in Mathematica :-)

1
2

g[r_] := Sum[IntegerExponent[r!, i], {i, 2, r}]
g[100]

Factorize each number from 2 to n (100 in this case) and factorize n!. Then, with that results, we can easily calculate f(n, i).

Note: code written in Boo

 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
46
47

def min(list) as int:
    result=list[0];
    for i in range(1, len(list)):
        if list[i]<result:
            result=list[i];

    return result;

def factorize(n) as Hash:
    r=n;
    i=2;
    h={};

    i=2;
    while r>1:
        while r%i==0:
            r/=i;
            if h[i]==null:
                h[i]=0;
            h[i]=h[i]+1;
        i++;

    return h;

def zerodigits(n as int) as int:
    memo=array(Hash, n+1);

    for i in range(2, n+1):
        memo[i]=factorize(i);

    allin={}

    for i in range(2, n+1):
        for f in memo[i].Keys:
            if allin[f]==null:
                allin[f]=0;
            allin[f]=allin[f]+memo[i][f];

    totalDigits=0;

    for i in range(2, n+1):
        l=[];
        for f in memo[i].Keys:
            l.Add(allin[f]/memo[i][f]);
        totalDigits+=min(l);

    return totalDigits;