🚀 go-pugleaf

In <DMuJwF.734@cwi.nl>, dik@cwi.nl (Dik T. Winter) writes:

[deserved flamelet gunched...]

>What you and most other posters (except the one I saw in maple, and my
>own of course) forget is that if a number contains factors of 5 you have
>to be aware of all factors 5 plus the remainder divided by all those
>factors. 14! ends in 2, lets see what happens if you multiply by 15.
>First take the factor of 5; this will take 2 to 10 and a last digit
>of 1; but (as you already saw) that is not valid so the last digit will
>become 6.  Now you still have the remaining factor 3 which will take
>6 to 8.  And, indeed, the last non-zero digit of 15! is 8.
>
>Jochen Schoof's solution inherently used a similar table, but he ignored
>the possibility of multiple factors 5.  Which (in his case) did result
>for some factorials in odd last non-zero digits, and that can not happen
>(except for 0! and 1!).
>
>Using only the last k digits of the factorial (excluding trailing zeros)
>and the last l digits of the multiplier will ultimately lead to a
>period.  (The proof is fairly simple.)  But the last non-zero digit of
>the factorial does not show a period; the increasing number of factors 5
>that can occur in a single number prevent this.  So, all such methods
>will fail at some stage.  Taking care of all individual factors 5 solves
>this.
>
>But apparently this is a tough question indeed.  Even an old-timer like
>Jos Horsmeier fell into at least one of the traps.
>-- 
>dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
>home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

OK, let me try my hand at this problem.   It is clear by now that factors of
5 are a problem.  One way to eliminate them as mentioned above is to eliminate
them and then divide the (previous) factorial by 2 to compensate.  As noted,
this too will eventually fail.

Thus, the next iteration, which is to eliminate, but keep track of, all of the
factors of 2 as well.  Then, your "factorial" will always have a non-zero
rightmost digit.  But, you then have to compensate for the powers of 2 (minus
the powers of 10) that you have eliminated up to that point.  Multiplying the 
last digit of you "factorial" by the last digit of the _net_ powers of 2 will
readily yield the last non-zero digit of the factorial.

The program is as follows.  It has been compile and run, but I look forward
to having it proved incorrect by others...


/* Determine last non-zero digit in a factorial */
/* 
   General algorithm:
   1) Eliminate all powers of 2 as they come along.  Keep track of _net_
      number of powers of 2 (see next step).  Last digit of this
      factor is easy to determine in a look up table.
   2) Eliminate all powers of 5 as they come along.  Take away powers of
      2, leaving _net_ powers of 2,  to convert to powers of 10.
      There are always more powers of 2 than powers of 5.  
      All powers of 10 result in no change to last significant digit.
   3) Multiply remainder of factor with previous residual.  Truncate
      to last digit, and reserve for next iteration.  Multiply by
      last digit of _net_ powers of two, take last digit as answer.
   4) Print out result, and loop to next.
*/

#include <stdlib.h>
#include <stdio.h>

/* function prototypes */
unsigned long right_digit(unsigned long i);
unsigned long eliminate_fives(unsigned long *i);
unsigned long eliminate_twos(unsigned long *i);

int main(int argc, char * argv[]){

	/* keep track of powers of 5s, powers of 2s so far */
	unsigned long p_of_5 = 0ul;
	unsigned long p_of_2 = 0ul;

	static unsigned long lookup[4] = {6ul, 2ul, 4ul, 8ul};

	unsigned long loop, temp, one, l1, count;
	unsigned long k;

	/* get factorial to go to */
	if(argc<2){
		count = 10; /* no number given, print out a few... */
	}
	else{
		count = atol(argv[1]);
	}


	printf("/* Fact   LD      10's\n");

	/* special cases here - 0! and 1! */
 	printf("%8ld   %1ld %8ld\n", 0ul, 1ul, 0ul); 
	printf("%8ld   %1ld %8ld\n", 1ul, 1ul, 0ul);

	/* Initialize last digit */
	one  = 1ul;

	for(loop = 2ul; loop <= count; loop++){

		temp = loop;

		/* drop all 2's from next factor, keep track of number */
		p_of_2 += eliminate_twos(&temp);

		/* drop all 5's from factor */
		k = eliminate_fives(&temp);	
		p_of_5 += k;		/* keep track of total 5's */
		p_of_2 -= k;		/* eliminate 2's to make 10s */

		/* multiply remainder and take last digit (always non-zero) */
		one = right_digit(one*temp);

		/* now correct for all the powers of two so far */
		l1  = right_digit(one*lookup[(p_of_2 % 4)]);

		printf("%8ld   %ld %8ld\n", loop, l1, p_of_5);

	}

	return(0);

}

unsigned long right_digit(unsigned long i){
	return (i % 10ul);
}

/* returns number of powers of 5 found in this integer, alters integer */
unsigned long eliminate_fives(unsigned long *i){
	unsigned long q;

	q = 0ul;
	while(!(*i % 5ul)){
		*i = *i/5ul;
		q++;
	}
	return(q);
}

/* returns number of powers of 2 found in this integer, alters integer */
unsigned long eliminate_twos(unsigned long *i){
	unsigned long q;

	q = 0ul;
	while(!(*i % 2ul)){
		*i = *i/2ul;
		q++;
	}
	return(q);
}

Cheers, Jon Custer

(Dik -- greetings to all folks on the Kruislaan.  I spent 3 years across
the way from you at FOM-AMOLF.)