#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    3
    Rep Power
    0

    Last nonzero digit.


    Hi everyone, Iím trying to solve problem in which I have to calculate the last non-zero 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
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Oh nevermind. This formula is useless for last non-zero 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!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    3
    Rep Power
    0
    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
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    3
    Rep Power
    0
    Ok, thank you very much for your help. This solution works.

IMN logo majestic logo threadwatch logo seochat tools logo