Algorithms

cp9876 wrote:

The most important thing he should do is limit the testing to sqrt(N).

Arash Partow wrote:

I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.

cp9876 wrote:

This is much more efficient than testing the remaining 15,703 factors.

Ian Uy wrote:

It is said that the most complex structures built by mankind are software systems.

Ian Uy wrote:

Is it possible to get the rightmost NON-ZERO digit of a factorial without calculating for it?

static int fac_last_digit(int x)
{
    int res = x;
    int mod = 10;
    while (x > 1)
    {
        if ((res * (x - 1)) % mod == 0) mod *= 10;
        res = (res * (--x)) % mod;
    }
    return (res / (mod / 10));
}

private int rightmostNonzeroInFactorial(int n) {
	int result = 1;
	// factor ending on 1
	// no change
	// factor ending on 2
	int count2 = (n+8) / 10;
	// factor ending on 3
	int count3 = (n + 7) / 10;
	// factor ending on 4
	int count4 = (n + 6) / 10;
	// factor ending on 5
	int count5 = (n + 5) / 10;
	// factor ending on 6
	int count6 = (n + 4) / 10;
	// factor ending on 7
	int count7 = (n + 3) / 10;
	// factor ending on 8
	int count8 = (n + 2) / 10;
	// factor ending on 9
	int count9 = (n + 1) / 10;
	// factor ending on 0
	int count10 = (n + 0) / 10;
	count5 += count10;
	if (count5 != 0) {
		result = (result * rightmostNonzeroInFactorial(count5)) % 10;
		count2 -= count5;
	}
	count2 += 2 * count4;	// 4 = 2*2
	count2 += 3 * count8;	// 8 = 2*2*2
	count2 += 4 * count6;	// 16 = 2*2*2*2

	count3 += 2 * count9;	// 9 = 3*3;
	count3 += 3 * count7;	// 27 = 3*3*3

	int[] fact3 = new int[] { 1, 3, 9, 7 };	// 3^5 ends on 3
	result = (result * fact3[count3 % fact3.Length]) % 10;

	int[] fact2 = new int[] { 1, 2, 4, 8 };	// 2^5 ends on 2
	int factor2=fact2[count2 % fact2.Length];
	if (factor2 == 1 && count2 != 0) factor2 = 6;	// 2^4 = 16
	result = (result * factor2) % 10;

	return result;
}

Luc Pattyn [Forum Guidelines] [My Articles]

---

Voting for dummies? No thanks.

---

Luc Pattyn wrote:

countN tells me how many factors of n! end on digit N

count5 += count10;	
if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }

if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }
if (count10 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count10)) % 10;
   }

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 non-zero digit as 2^n x q! x r!

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 //= 5
    return result

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