All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Deux Digit Determination (Posted on 2014-11-13) Difficulty: 3 of 5
Find the last two digits in the base ten expansion of :

C(2014, 1) + 22*C(2014, 2) + 32*C(2014, 3) + ......+ 20142*C(2014, 2014)

**** C is the choose function, that is:
C(m,n) = m!/(n!*(m-n)!)

See The Solution Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 2 of 4 |
   10   for I=1 to 2014
   15   print I
   20      Tot=Tot+I*I*fnComb(2014,I)
   30   next
   40   print Tot
   49   kill "deuxdigd.txt"
   50   open "deuxdigd.txt" for output as #2
   55   print #2,Tot
   60   close #2
  999   end
 1010   fnComb(A,B)
 1020   N=A:R=B:if R>N/2 then R=N-R
 1030   Prod=1:Lst=R+1
 1040   for Trm=N to N-R+1 step -1
 1050    if Trm@2=0 and Trm/2<=R then
 1055      :Prod=Prod*2:Lst=Trm\2
 1056     :else Prod=Prod*Trm
 1060   next
 1070   for Trm=Lst-1 to 2 step -1
 1080     Prod=Prod\Trm
 1090   next
 1100   return(Prod)

finds the full total is

 1908472000048714732661524899983884617473724383966561791807641407903208611694645711419
 8974848878628493908937106053469435092299090485919988844732534328971565561802043934695
 3317507725398190972613631050377543821533394303057793320718222317421129010250122177849
 9035473101735814951671037282629915705987101664148646943619924499740065876510511277362
 8435347968792240373068389007196638524154770333659178536752609555291836789051310377412
 9045165616305577077474605364391754059142314121308955215038889916907354563541911024597
 7735711758243022145680192954075648251244176622850884474203288652844896975192523719412
 865034256289628160 
 
so the last two digits are 60.

 
The program avoids overflow by not fully calculating the factorials. For example, C(20,7) is done via:

20*19*18*17*16*15*2
-------------------
    6*5*4*3*2*1
    
Note the 7 is left out of this denominator as 2 was substituted for 14 in the numerator, as is the case whenever half a factor in the numerator overlaps with a number needed in the denominator. And of course the numbers in the numerator below 14 are not considered at all, so as to obviate the necessity of dividing by 13!.

Also, C(20,13) would be considered as C(20,7) before the algorithm is run.
 

The largest C(n,r) needed was of course C(2014,1007):
 
3344010913972733623838912657833260535422254486653877800815687761624264790254014089103728724107550881
0325026409216813829145638949835383318837409995156192718059082430562723496812588052915029275583516886
2599589092078667722329069251638821031080353533821109539142043069422888264480190438106835292350985374
3960709704999779854871120847954453384426805514414613102005970516751428204977908760812460792410949945
1754282735700404398220305067187559956114475217389866747569564770389041134189592172661730885555135294
8785544643829199777415417954714158264251413529910907087010903116901599447604910754772847842763845026
27840 


  Posted by Charlie on 2014-11-13 14:24:33
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information