Reduce mod 10 the numbers 2..n and then cancel out the required factors of 10. The final step then involves computing 2^i*3^j*7^k mod 10 for suitable i,j and k.
A small program that performs this calculation is appended. Like the other solutions, it takes O(log n) arithmetic operations.
- kym
===
- include<stdio.h>
- include<assert.h>
/2/ 2, 4, 8, 6, /3/ 3, 9, 7, 1, /4/ 4, 6, 4, 6, /5/ 5, 5, 5, 5, /6/ 6, 6, 6, 6, /7/ 7, 9, 3, 1, };
main(){
int i; int n;
for(n=2;n<1000;n++){
i=lsdfact(n); printf("%d\n",i); }
exit(0); }
lsdfact(n){
int a10?; int i; int n5; int tmp;
for(i=0;i<=9;i++)ai?=alpha(i,n);
n5=0;
/* NOTE: order is important in following */ l5:;
while(tmp=a5?){ /* cancel factors of 5 */
n5+=tmp; a1?+=(tmp+4)/5; a3?+=(tmp+3)/5; a5?=(tmp+2)/5; a7?+=(tmp+1)/5; a9?+=(tmp+0)/5; }
l10:;
if(tmp=a0?){
a0?=0; /* cancel all factors of 10 */ for(i=0;i<=9;i++)ai?+=alpha(i,tmp); }
/* n5 == number of 5's cancelled;
must now cancel same number of factors of 2 */
i=ipow(2,a2?+2*a4?+a6?+3*a8?-n5)*
assert(i%10); /* must not be zero */ return i%10; }
alpha(d,n){ /* number of decimal numbers in 1,n? ending in digit d */
int tmp; tmp=(n+10-d)/10; if(d==0)tmp--; /* forget 0 */ return tmp; }
ipow(x,y){ /* x^y mod 10 */
if(y==0) return 1; if(y==1) return x; return px-2?(y-1)%4?; }