Can a factorials (say 1457982) last non-zero digit be found without calculation of that factorial, why, how?
Posted on 2003-09-02 15:02:43 by inFinie
Yes you can do it. For trailing zero digits to base 2 it's easy.

Base2TrailingZeros = N - NumberOfBits(N).

In this group here you should read the other Binomial posting. The primepower extraction can be used to compute the traling zero digits to any other base.

To base 3 we have to examine the prime power to base 3. Then we have to convert N to a base 3 Number an subtract such as above. Now if you print N! to base 3 then we get withhelp of the powerextraction the number of trailing zero digits to base 3.

Sometimes i wrote a small source to compute the trailing zero digits to base 10. I should again search it now :) The goal was to compute the first ten trailing non-zero digits of any factorial.
You have to compute the prime power extraction. Then you strike out all prime powers thats lead to trailing zero digits to the resulting base. After this we multiply out the prime power table BUT any operation as modular operation to lets say 10^10. We get the 10 trailing Non-zero digits to base 10.
For base 10 you fully ignore base 5 power and subtracts this exponent from the base 2 power.
The remaining prime powers are multiplied mod 10^10.

For base 2 we have easily to ignore the prime power to base 2 in the computation, and do all operations truncated only to 32bit. Eg. thats the same as we do modulo 2^32. Finally we get the first 32 non zero bits of N!.

In fact this very fast method was used to crosscheck my computation.

Many times harder was to compute the first ten leading digits of such functions :)

Regards, Hagen
Posted on 2003-09-02 17:22:56 by Hagen