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

===

1. include<stdio.h>
2. include<assert.h>

int p6?4?={

/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); }

if(a5?) goto l5; if(a0?) goto l10;

/* 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)*

ipow(3,a3?+a6?+2*a9?)* ipow(7,a7?);

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?; }

lib/config.php:156: Notice: Undefined variable: accept

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access