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

 Deux Digit Determination (Posted on 2014-11-13)
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.)
 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

 Search: Search body:
Forums (0)