
Nice try, but you will quickly fall over without a large integer class. Even 1000! ends with 249 zeros, so mod will grow to about 10^249 or so.
If you get bored, try to write a routine to compute the last nonzero digit of googol! = (10^100)!, you should get 6.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Hi Peter,
IMO this will behave much better; it gives 4 for 10000000, does not overflow,
has no loops but uses a recursion (scaling down by a factor of 5).
private int rightmostNonzeroInFactorial(int n) {
int result = 1;
int count2 = (n+8) / 10;
int count3 = (n + 7) / 10;
int count4 = (n + 6) / 10;
int count5 = (n + 5) / 10;
int count6 = (n + 4) / 10;
int count7 = (n + 3) / 10;
int count8 = (n + 2) / 10;
int count9 = (n + 1) / 10;
int count10 = (n + 0) / 10;
count5 += count10;
if (count5 != 0) {
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
count2 += 2 * count4; count2 += 3 * count8; count2 += 4 * count6;
count3 += 2 * count9; count3 += 3 * count7;
int[] fact3 = new int[] { 1, 3, 9, 7 }; result = (result * fact3[count3 % fact3.Length]) % 10;
int[] fact2 = new int[] { 1, 2, 4, 8 }; int factor2=fact2[count2 % fact2.Length];
if (factor2 == 1 && count2 != 0) factor2 = 6; result = (result * factor2) % 10;
return result;
}
Main principle is factors that are not multiples of 5 don't care about their
digits except the lowest one (and also: there will be more powers of 2 than
powers of 5).





Hi Luc,
I haven't worked through your code (are you sure the countN's do the right thing?).
There is a little known fact (don't ask me how I know it!) that
if n = 5q+r with 0 <= r < 5
then n! has the same rightmost nonzero digit as 2^n x q! x r!
Using this the problems reduce easily.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Hi Peter,
1.
countN tells me how many factors of n! end on digit N
2.
the recursion takes care of your q!
3.
I ran a check for all [1,500] and for 10000000
regards,





Luc Pattyn wrote: countN tells me how many factors of n! end on digit N
OK now I see what you are doing. I'm sure you have some very clever reason for this, but it is not clear to me why you do
count5 += count10;
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
and not what I would expect:
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
if (count10 != 0)
{
result = (result * rightmostNonzeroInFactorial(count10)) % 10;
}
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Hi Peter,
the way you propose the factors that end on 5 don't get represented by count5 factorial
(they only need odd multiples of 5), hence the recursion would not be correct.
I expect the theory that explains my code would be the same as the one that led to the
formula you've mentioned before.





Ah now I see (it's late here
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





cp9876 wrote: ...There is a little known fact (don't ask me how I know it!) that
if n = 5q+r with 0 <= r < 5
then n! has the same rightmost nonzero digit as 2^n x q! x r!
That should be 2^q rather than 2^n, and then it's valid for all n > 4. Removing recursion, here's one way to write it (in Python):
def f(n):
result = 1
while n > 1:
n, r = divmod(n, 5)
result = result * (6, 2, 4, 8)[n & 3] * (1, 1, 2, 6, 4)[r] % 10
return result
and that can be simplified a bit by using a larger table:
FACTAB = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2
def f(n):
result = 1
while n > 1:
result = result * FACTAB[n % 20] % 10
n return result





I believe this to be an ACM question from either 96' or 97'
bool nonzerodigit(const unsigned int& n, unsigned int& result)
{
if (n > 100000) return false;
unsigned int result = 1;
for (unsigned int i = 1; i <= n; ++i)
{
unsigned int f = i;
while (0 == (f % 5))
{
f /= 5;
result /= 2;
}
result = (result % 100000) * f;
}
result %= 10;
return true;
}
100000 is an upper sanity bound and also a quantizer for the minimum required 6 "least significant" digits.





Thank you!
I am training for the next ACM ICPC Regionals.
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.



