Last nonzero digit of a factorial

Question

I want to determine the last nonzero digit of a factorial.

I tried to solve it using division: Dividing the number by 10 or multiples thereof.

Ex : 7! = 5040 => 4

So I divide 5040 by 10 and get 4 as result.

But, let us say, we should use the number 7 in the logic instead of value of the factorial (5040).

Please let me know how can I do it?

Answer 1

1. Compute the prime decomposition of n! as follows:
   • for each prime p <= n, the exponent of p is
     
2. Subtract the exponent of 5 from the exponent of 2 and discard all the fives from the prime decomposition.
3. Multiply the remaining prime decomposition modulo 10. Note that when doing this, you can use the following equivalence: (for i ≥ 0). The individual products can also be done mod 10 if necessary.

---

I used a bit of spare time to implement this solution in bash. (bash? well, why not?):

last_nonzero () { 
    local n=$1
    local d=$(power_mod_10 3 $(count_factors $n 3))
    d=$((d * $(power_mod_10 2 $(($(count_factors $n 2)
                               - $(count_factors $n 5))))))
    for p in $(primes 7 $n)
    do
        d=$((d * $(power_mod_10 $p $(count_factors $n $p)) % 10))
    done
    echo $d
}

count_factors () { 
    local n=$1 p=$2
    local d=$((n/p))
    local q=$d
    while ((q >= p)); do
        q=$((q/p)) d=$((d+q))
    done
    echo $d
}

power_mod_10 () { 
    local mods=..........0161000101012300070901490009010187000309
    local p=$(($1%10)) exp=$(($2%4+1))
    echo ${mods:$exp$p:1}
}

Yes, the last one is a hack.

Also: There is an even better recursive solution. Search http://math.stackexchange.com, or even google.