September 30th, 2012, 07:03 PM

Last nonzero digit.
Hi everyone, I’m trying to solve problem in which I have to calculate the last nonzero digit of this:
(a1+a2+a3+..+an)!/(a1!*a2!*a3!*..*an!), where 0 ≤ ai ≤ 1000000000 and n ≤ 20.
It's obvious, that the “brutal” counting this is a bad solution (counting the one billion factorial takes too much time and memory). Another solution is an attempt to shorten. I write numerator and denominator is a simplified form (for example: 5!=1*2*3*4*5) and I’m reducing until the denominator = 1, then I’m starting to multiplies (with using my own arithmetic for large numbers) numbers that I got. This solution, in turn, doesn’t work because there is no space in the memory for a sufficiently large array (for the awarding of the numerator and denominator), on the other hand, because even after reducing, the numbers are too big for it to multiply them at the right time. Another idea was to calculate the common logarithm of that number, but the solution isn’t valid because of too little precision of long double variable. I have no other ideas for solving this problem, so please help me with it.
Examples:
n=2, a1=11, a2=9
Result: 6
n=4, a1=2, a2=5, a3=7, a4=9
Result: 8
September 30th, 2012, 08:45 PM

Begin by canceling out factors of 2 and 5 in the numerator and denominator. A 5 in the numerator also cancels a 2 in the numerator, since together they give you 10, which just adds a zero to the end of the result. After all this cancelation, only the last digit of each factor in the numerator and denominator matters. I leave you to ponder this, just giving one example:
Code:
(11 + 9)!/(11! * 9!)
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
= 
(1 2 3 4 5 6 7 8 9 10 11) (1 2 3 4 5 6 7 8 9)
(2^18 5^4 (1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1))
= 
(2^8 5^2 (1 1 3 1 13 7 1 9 1 11)) (2^7 5^1 (1 1 3 1 1 3 7 1 9))
(1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1)
= (2^3 5^1) 
(1 1 3 1 1 3 7 1 9 1 11) (1 1 3 1 1 3 7 1 9)
(1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1)
> (2 2) 
(1 1 3 1 1 3 7 1 9 1 11) (1 1 3 1 1 3 7 1 9)
(...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9 ...1 ...1 ...3 ...3 ...7 ...3 ...1 ...7 ...9 ...9 ...1)
> (2 2) 
(...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9 ...1 ...1) (...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9)
Everything is now reduced to arithmetic modulo 10, so no more big numbers.
If you're wondering whether you can "divide" mod 10: suppose X ends with 7 and Y ends with 3, and X/Y is an integer. What does X/Y end with? Well, (X/Y)*Y = X. Since Y ends with 3 and X ends with 7, X/Y can only end with 9.
October 1st, 2012, 10:31 AM

Oh nevermind. This formula is useless for last nonzero digit.
Given that I didn't actually read the original post or the answer of the eternal light, Stirling's formula is pretty good for enormous factorials and of course you must know a quick way to add arithmetic sequences.
Last edited by b49P23TIvg; October 1st, 2012 at 10:34 AM.
[code]
Code tags[/code] are essential for python code and Makefiles!
October 1st, 2012, 12:35 PM

Originally Posted by Lux Perpetua
Begin by canceling out factors of 2 and 5 in the numerator and denominator. A 5 in the numerator also cancels a 2 in the numerator, since together they give you 10, which just adds a zero to the end of the result. After all this cancelation,
only the last digit of each factor in the numerator and denominator matters. I leave you to ponder this, just giving one example:
Code:
(11 + 9)!/(11! * 9!)
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
= 
(1 2 3 4 5 6 7 8 9 10 11) (1 2 3 4 5 6 7 8 9)
(2^18 5^4 (1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1))
= 
(2^8 5^2 (1 1 3 1 13 7 1 9 1 11)) (2^7 5^1 (1 1 3 1 1 3 7 1 9))
(1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1)
= (2^3 5^1) 
(1 1 3 1 1 3 7 1 9 1 11) (1 1 3 1 1 3 7 1 9)
(1 1 3 1 1 3 7 1 9 1 11 3 13 7 3 1 17 9 19 1)
> (2 2) 
(1 1 3 1 1 3 7 1 9 1 11) (1 1 3 1 1 3 7 1 9)
(...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9 ...1 ...1 ...3 ...3 ...7 ...3 ...1 ...7 ...9 ...9 ...1)
> (2 2) 
(...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9 ...1 ...1) (...1 ...1 ...3 ...1 ...1 ...3 ...7 ...1 ...9)
Everything is now reduced to arithmetic modulo 10, so no more big numbers.
If you're wondering whether you can "divide" mod 10: suppose X ends with 7 and Y ends with 3, and X/Y is an integer. What does X/Y end with? Well, (X/Y)*Y = X. Since Y ends with 3 and X ends with 7, X/Y can only end with 9.
What if the numerator = 2 and denominator = 8. What will be the result?
Examples:
1)
numerator = 6! = 720
denominator = 2!*2!*2! = 8
6!/(2!*2!*2!) = 90
2)
numerator = 36! = 371993326789901217467999448150835200000000
denominator = 1!*1!*4!*7!*4!*8!*9!*2! = 84950623715328000
36!/(1!*1!*4!*7!*4!*8!*9!*2!) = 4378935792590077118400000
October 2nd, 2012, 01:10 AM

Originally Posted by paper01
What if the numerator = 2 and denominator = 8. What will be the result?
Examples:
1)
numerator = 6! = 720
denominator = 2!*2!*2! = 8
6!/(2!*2!*2!) = 90
2)
numerator = 36! = 371993326789901217467999448150835200000000
denominator = 1!*1!*4!*7!*4!*8!*9!*2! = 84950623715328000
36!/(1!*1!*4!*7!*4!*8!*9!*2!) = 4378935792590077118400000
That's why you eliminate all factors of 2 and 5 first from both the numerator and denominator.
371993326789901217467999448150835200000000 = (2^34) (5^8) 55431325255319657544493593.
84950623715328000 = (2^25) (5^3) 20253807.
36!/(1!*1!*4!*7!*4!*8!*9!*2!) = (2^9) (5^5) 55431325255319657544493593/20253807,
which has the same last nonzero digit as (2^4) 55431325255319657544493593/20253807,
and this last number has no zeros at the end (not being divisible by 5).
3/7 (mod 10) is 9 (since 7*9 = 63).
9*(2^4) (mod 10) is 9*2*2*2*2 (mod 10), which is 4.
Theorem. If A and B are positive integers not divisible by 2 or 5, then the last digit of A/B (if it is an integer) is uniquely determined by the last digit of A and the last digit of B.
October 6th, 2012, 08:44 AM

Ok, thank you very much for your help. This solution works.