## Project Euler: Problem 13

Problem thirteen from Project Euler is one of those problems that's so simple, I don't understand why it's in the double digits section. The problem reads: “Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.”
It then proceeds to list 100 long numbers. I'm not going to paste them here because they are in the code solutions below and I don't want to clog up the “tubez” with more redundant information than I'm about to.

Enough of my jibber-jabber. Here is my Haskell solution first (trying to change things up here):

1. module Main where
2.
3. main :: IO()
4. main = do
5. print . take 10 . show \$ sum big_number
6. where big_number = [ 37107287533902102798797998220837590246510135740250
7. , 46376937677490009712648124896970078050417018260538
8. , 74324986199524741059474233309513058123726617309629
9. , 91942213363574161572522430563301811072406154908250
10. , 23067588207539346171171980310421047513778063246676
11. , 89261670696623633820136378418383684178734361726757
12. , 28112879812849979408065481931592621691275889832738
13. , 44274228917432520321923589422876796487670272189318
14. , 47451445736001306439091167216856844588711603153276
15. , 70386486105843025439939619828917593665686757934951
16. , 62176457141856560629502157223196586755079324193331
17. , 64906352462741904929101432445813822663347944758178
18. , 92575867718337217661963751590579239728245598838407
19. , 58203565325359399008402633568948830189458628227828
20. , 80181199384826282014278194139940567587151170094390
21. , 35398664372827112653829987240784473053190104293586
22. , 86515506006295864861532075273371959191420517255829
23. , 71693888707715466499115593487603532921714970056938
24. , 54370070576826684624621495650076471787294438377604
25. , 53282654108756828443191190634694037855217779295145
26. , 36123272525000296071075082563815656710885258350721
27. , 45876576172410976447339110607218265236877223636045
28. , 17423706905851860660448207621209813287860733969412
29. , 81142660418086830619328460811191061556940512689692
30. , 51934325451728388641918047049293215058642563049483
31. , 62467221648435076201727918039944693004732956340691
32. , 15732444386908125794514089057706229429197107928209
33. , 55037687525678773091862540744969844508330393682126
34. , 18336384825330154686196124348767681297534375946515
35. , 80386287592878490201521685554828717201219257766954
36. , 78182833757993103614740356856449095527097864797581
37. , 16726320100436897842553539920931837441497806860984
38. , 48403098129077791799088218795327364475675590848030
39. , 87086987551392711854517078544161852424320693150332
40. , 59959406895756536782107074926966537676326235447210
41. , 69793950679652694742597709739166693763042633987085
42. , 41052684708299085211399427365734116182760315001271
43. , 65378607361501080857009149939512557028198746004375
44. , 35829035317434717326932123578154982629742552737307
45. , 94953759765105305946966067683156574377167401875275
46. , 88902802571733229619176668713819931811048770190271
47. , 25267680276078003013678680992525463401061632866526
48. , 36270218540497705585629946580636237993140746255962
49. , 24074486908231174977792365466257246923322810917141
50. , 91430288197103288597806669760892938638285025333403
51. , 34413065578016127815921815005561868836468420090470
52. , 23053081172816430487623791969842487255036638784583
53. , 11487696932154902810424020138335124462181441773470
54. , 63783299490636259666498587618221225225512486764533
55. , 67720186971698544312419572409913959008952310058822
56. , 95548255300263520781532296796249481641953868218774
57. , 76085327132285723110424803456124867697064507995236
58. , 37774242535411291684276865538926205024910326572967
59. , 23701913275725675285653248258265463092207058596522
60. , 29798860272258331913126375147341994889534765745501
61. , 18495701454879288984856827726077713721403798879715
62. , 38298203783031473527721580348144513491373226651381
63. , 34829543829199918180278916522431027392251122869539
64. , 40957953066405232632538044100059654939159879593635
65. , 29746152185502371307642255121183693803580388584903
66. , 41698116222072977186158236678424689157993532961922
67. , 62467957194401269043877107275048102390895523597457
68. , 23189706772547915061505504953922979530901129967519
69. , 86188088225875314529584099251203829009407770775672
70. , 11306739708304724483816533873502340845647058077308
71. , 82959174767140363198008187129011875491310547126581
72. , 97623331044818386269515456334926366572897563400500
73. , 42846280183517070527831839425882145521227251250327
74. , 55121603546981200581762165212827652751691296897789
75. , 32238195734329339946437501907836945765883352399886
76. , 75506164965184775180738168837861091527357929701337
77. , 62177842752192623401942399639168044983993173312731
78. , 32924185707147349566916674687634660915035914677504
79. , 99518671430235219628894890102423325116913619626622
80. , 73267460800591547471830798392868535206946944540724
81. , 76841822524674417161514036427982273348055556214818
82. , 97142617910342598647204516893989422179826088076852
83. , 87783646182799346313767754307809363333018982642090
84. , 10848802521674670883215120185883543223812876952786
85. , 71329612474782464538636993009049310363619763878039
86. , 62184073572399794223406235393808339651327408011116
87. , 66627891981488087797941876876144230030984490851411
88. , 60661826293682836764744779239180335110989069790714
89. , 85786944089552990653640447425576083659976645795096
90. , 66024396409905389607120198219976047599490197230297
91. , 64913982680032973156037120041377903785566085089252
92. , 16730939319872750275468906903707539413042652315011
93. , 94809377245048795150954100921645863754710598436791
94. , 78639167021187492431995700641917969777599028300699
95. , 15368713711936614952811305876380278410754449733078
96. , 40789923115535562561142322423255033685442488917353
97. , 44889911501440648020369068063960672322193204149535
98. , 41503128880339536053299340368006977710650566631954
99. , 81234880673210146739058568557934581403627822703280
100. , 82616570773948327592232845941706525094512325230608
101. , 22918802058777319719839450180888072429661980811197
102. , 77158542502016545090413245809786882778948721859617
103. , 72107838435069186155435662884062257473692284509516
104. , 20849603980134001723930671666823555245252804609722
105. , 53503534226472524250874054075591789781264330331690]

followed by my Python solution:

1. #!/usr/bin/python
2. """
3. code solution for project euler's problem #13 in python.
4. """
5. from __future__ import print_function
6.
7. def print_10(number):
8. print(str(number)[0:10])
9.
10. if __name__ == "__main__":
11.
12. big_number = [ 37107287533902102798797998220837590246510135740250,
13. 46376937677490009712648124896970078050417018260538,
14. 74324986199524741059474233309513058123726617309629,
15. 91942213363574161572522430563301811072406154908250,
16. 23067588207539346171171980310421047513778063246676,
17. 89261670696623633820136378418383684178734361726757,
18. 28112879812849979408065481931592621691275889832738,
19. 44274228917432520321923589422876796487670272189318,
20. 47451445736001306439091167216856844588711603153276,
21. 70386486105843025439939619828917593665686757934951,
22. 62176457141856560629502157223196586755079324193331,
23. 64906352462741904929101432445813822663347944758178,
24. 92575867718337217661963751590579239728245598838407,
25. 58203565325359399008402633568948830189458628227828,
26. 80181199384826282014278194139940567587151170094390,
27. 35398664372827112653829987240784473053190104293586,
28. 86515506006295864861532075273371959191420517255829,
29. 71693888707715466499115593487603532921714970056938,
30. 54370070576826684624621495650076471787294438377604,
31. 53282654108756828443191190634694037855217779295145,
32. 36123272525000296071075082563815656710885258350721,
33. 45876576172410976447339110607218265236877223636045,
34. 17423706905851860660448207621209813287860733969412,
35. 81142660418086830619328460811191061556940512689692,
36. 51934325451728388641918047049293215058642563049483,
37. 62467221648435076201727918039944693004732956340691,
38. 15732444386908125794514089057706229429197107928209,
39. 55037687525678773091862540744969844508330393682126,
40. 18336384825330154686196124348767681297534375946515,
41. 80386287592878490201521685554828717201219257766954,
42. 78182833757993103614740356856449095527097864797581,
43. 16726320100436897842553539920931837441497806860984,
44. 48403098129077791799088218795327364475675590848030,
45. 87086987551392711854517078544161852424320693150332,
46. 59959406895756536782107074926966537676326235447210,
47. 69793950679652694742597709739166693763042633987085,
48. 41052684708299085211399427365734116182760315001271,
49. 65378607361501080857009149939512557028198746004375,
50. 35829035317434717326932123578154982629742552737307,
51. 94953759765105305946966067683156574377167401875275,
52. 88902802571733229619176668713819931811048770190271,
53. 25267680276078003013678680992525463401061632866526,
54. 36270218540497705585629946580636237993140746255962,
55. 24074486908231174977792365466257246923322810917141,
56. 91430288197103288597806669760892938638285025333403,
57. 34413065578016127815921815005561868836468420090470,
58. 23053081172816430487623791969842487255036638784583,
59. 11487696932154902810424020138335124462181441773470,
60. 63783299490636259666498587618221225225512486764533,
61. 67720186971698544312419572409913959008952310058822,
62. 95548255300263520781532296796249481641953868218774,
63. 76085327132285723110424803456124867697064507995236,
64. 37774242535411291684276865538926205024910326572967,
65. 23701913275725675285653248258265463092207058596522,
66. 29798860272258331913126375147341994889534765745501,
67. 18495701454879288984856827726077713721403798879715,
68. 38298203783031473527721580348144513491373226651381,
69. 34829543829199918180278916522431027392251122869539,
70. 40957953066405232632538044100059654939159879593635,
71. 29746152185502371307642255121183693803580388584903,
72. 41698116222072977186158236678424689157993532961922,
73. 62467957194401269043877107275048102390895523597457,
74. 23189706772547915061505504953922979530901129967519,
75. 86188088225875314529584099251203829009407770775672,
76. 11306739708304724483816533873502340845647058077308,
77. 82959174767140363198008187129011875491310547126581,
78. 97623331044818386269515456334926366572897563400500,
79. 42846280183517070527831839425882145521227251250327,
80. 55121603546981200581762165212827652751691296897789,
81. 32238195734329339946437501907836945765883352399886,
82. 75506164965184775180738168837861091527357929701337,
83. 62177842752192623401942399639168044983993173312731,
84. 32924185707147349566916674687634660915035914677504,
85. 99518671430235219628894890102423325116913619626622,
86. 73267460800591547471830798392868535206946944540724,
87. 76841822524674417161514036427982273348055556214818,
88. 97142617910342598647204516893989422179826088076852,
89. 87783646182799346313767754307809363333018982642090,
90. 10848802521674670883215120185883543223812876952786,
91. 71329612474782464538636993009049310363619763878039,
92. 62184073572399794223406235393808339651327408011116,
93. 66627891981488087797941876876144230030984490851411,
94. 60661826293682836764744779239180335110989069790714,
95. 85786944089552990653640447425576083659976645795096,
96. 66024396409905389607120198219976047599490197230297,
97. 64913982680032973156037120041377903785566085089252,
98. 16730939319872750275468906903707539413042652315011,
99. 94809377245048795150954100921645863754710598436791,
100. 78639167021187492431995700641917969777599028300699,
101. 15368713711936614952811305876380278410754449733078,
102. 40789923115535562561142322423255033685442488917353,
103. 44889911501440648020369068063960672322193204149535,
104. 41503128880339536053299340368006977710650566631954,
105. 81234880673210146739058568557934581403627822703280,
106. 82616570773948327592232845941706525094512325230608,
107. 22918802058777319719839450180888072429661980811197,
108. 77158542502016545090413245809786882778948721859617,
109. 72107838435069186155435662884062257473692284509516,
110. 20849603980134001723930671666823555245252804609722,
111. 53503534226472524250874054075591789781264330331690]
112.
113. print_10(sum(big_number))

and to continue adding in the spice, I have included a solution in Scala:

1. import BigInt._
2.
3. object problem_13 {
4. def main (args : Array[String]){
5. val big_number = List("37107287533902102798797998220837590246510135740250",
6. "46376937677490009712648124896970078050417018260538",
7. "74324986199524741059474233309513058123726617309629",
8. "91942213363574161572522430563301811072406154908250",
9. "23067588207539346171171980310421047513778063246676",
10. "89261670696623633820136378418383684178734361726757",
11. "28112879812849979408065481931592621691275889832738",
12. "44274228917432520321923589422876796487670272189318",
13. "47451445736001306439091167216856844588711603153276",
14. "70386486105843025439939619828917593665686757934951",
15. "62176457141856560629502157223196586755079324193331",
16. "64906352462741904929101432445813822663347944758178",
17. "92575867718337217661963751590579239728245598838407",
18. "58203565325359399008402633568948830189458628227828",
19. "80181199384826282014278194139940567587151170094390",
20. "35398664372827112653829987240784473053190104293586",
21. "86515506006295864861532075273371959191420517255829",
22. "71693888707715466499115593487603532921714970056938",
23. "54370070576826684624621495650076471787294438377604",
24. "53282654108756828443191190634694037855217779295145",
25. "36123272525000296071075082563815656710885258350721",
26. "45876576172410976447339110607218265236877223636045",
27. "17423706905851860660448207621209813287860733969412",
28. "81142660418086830619328460811191061556940512689692",
29. "51934325451728388641918047049293215058642563049483",
30. "62467221648435076201727918039944693004732956340691",
31. "15732444386908125794514089057706229429197107928209",
32. "55037687525678773091862540744969844508330393682126",
33. "18336384825330154686196124348767681297534375946515",
34. "80386287592878490201521685554828717201219257766954",
35. "78182833757993103614740356856449095527097864797581",
36. "16726320100436897842553539920931837441497806860984",
37. "48403098129077791799088218795327364475675590848030",
38. "87086987551392711854517078544161852424320693150332",
39. "59959406895756536782107074926966537676326235447210",
40. "69793950679652694742597709739166693763042633987085",
41. "41052684708299085211399427365734116182760315001271",
42. "65378607361501080857009149939512557028198746004375",
43. "35829035317434717326932123578154982629742552737307",
44. "94953759765105305946966067683156574377167401875275",
45. "88902802571733229619176668713819931811048770190271",
46. "25267680276078003013678680992525463401061632866526",
47. "36270218540497705585629946580636237993140746255962",
48. "24074486908231174977792365466257246923322810917141",
49. "91430288197103288597806669760892938638285025333403",
50. "34413065578016127815921815005561868836468420090470",
51. "23053081172816430487623791969842487255036638784583",
52. "11487696932154902810424020138335124462181441773470",
53. "63783299490636259666498587618221225225512486764533",
54. "67720186971698544312419572409913959008952310058822",
55. "95548255300263520781532296796249481641953868218774",
56. "76085327132285723110424803456124867697064507995236",
57. "37774242535411291684276865538926205024910326572967",
58. "23701913275725675285653248258265463092207058596522",
59. "29798860272258331913126375147341994889534765745501",
60. "18495701454879288984856827726077713721403798879715",
61. "38298203783031473527721580348144513491373226651381",
62. "34829543829199918180278916522431027392251122869539",
63. "40957953066405232632538044100059654939159879593635",
64. "29746152185502371307642255121183693803580388584903",
65. "41698116222072977186158236678424689157993532961922",
66. "62467957194401269043877107275048102390895523597457",
67. "23189706772547915061505504953922979530901129967519",
68. "86188088225875314529584099251203829009407770775672",
69. "11306739708304724483816533873502340845647058077308",
70. "82959174767140363198008187129011875491310547126581",
71. "97623331044818386269515456334926366572897563400500",
72. "42846280183517070527831839425882145521227251250327",
73. "55121603546981200581762165212827652751691296897789",
74. "32238195734329339946437501907836945765883352399886",
75. "75506164965184775180738168837861091527357929701337",
76. "62177842752192623401942399639168044983993173312731",
77. "32924185707147349566916674687634660915035914677504",
78. "99518671430235219628894890102423325116913619626622",
79. "73267460800591547471830798392868535206946944540724",
80. "76841822524674417161514036427982273348055556214818",
81. "97142617910342598647204516893989422179826088076852",
82. "87783646182799346313767754307809363333018982642090",
83. "10848802521674670883215120185883543223812876952786",
84. "71329612474782464538636993009049310363619763878039",
85. "62184073572399794223406235393808339651327408011116",
86. "66627891981488087797941876876144230030984490851411",
87. "60661826293682836764744779239180335110989069790714",
88. "85786944089552990653640447425576083659976645795096",
89. "66024396409905389607120198219976047599490197230297",
90. "64913982680032973156037120041377903785566085089252",
91. "16730939319872750275468906903707539413042652315011",
92. "94809377245048795150954100921645863754710598436791",
93. "78639167021187492431995700641917969777599028300699",
94. "15368713711936614952811305876380278410754449733078",
95. "40789923115535562561142322423255033685442488917353",
96. "44889911501440648020369068063960672322193204149535",
97. "41503128880339536053299340368006977710650566631954",
98. "81234880673210146739058568557934581403627822703280",
99. "82616570773948327592232845941706525094512325230608",
100. "22918802058777319719839450180888072429661980811197",
101. "77158542502016545090413245809786882778948721859617",
102. "72107838435069186155435662884062257473692284509516",
103. "20849603980134001723930671666823555245252804609722",
104. "53503534226472524250874054075591789781264330331690") map {BigInt(_)}
105. val sums = big_number sum
106. val su = sums toString
107. val su10 = su take 10
108. println(su10)
109. }
110. }

Some of you may be wondering, “Why a Scala solution?” To which I respond, “Why not?” Because that's a little short, I'll add that it has something to do with Scala starting to gain traction in the industry and me seeing if I would like to get paid to program in it.

The solution, in all three languages, is pretty simple. The recipe essentially says, “Put all numbers into a list. Get the sum of that list, turn that number into a string, and get the first 10 characters of that string.”

Times:
Python : real 0m0.059s
Scala (compiled) : real 0m0.757s

For the most part it's pretty standard in these tests to see performance times such that Haskell (compiled) < Python < Haskell (runghc). Java and Perl usually fall somewhere between the Haskell (compiled) and Python, in that order. To see Scala be 2x slower than Haskell (runghc) was a shocker. The only thing that makes sense to me for the slowdown is having to use the BigInt library. That is probably the biggest thing I took away from these time tests - if I want to do REALLY large number crunching and performance DOES matter, JVM-based languages might not be the best option.

A few thoughts on Scala:
If I haven't stated it already in this blog, I should now give the disclaimer that I'm not a Java fan. I know it still has its loyal followers, but I'm not one of them. Moving on. This was my first time working with Scala, and I'd like to finally welcome Java to the 21st century. While doing some research on the Scala language itself I read that “the industry” was moving to replace Java with Scala. I welcome that change. Does that mean I “like” Scala? The honest answer is, to butcher the quote the appliances from the Flintstones, “Eh, it's a language.” Scala is definitely an improvement over Java – not really that hard to do in my opinion – but, the language still feels unpolished. One quick way to kill the interpreter in Scala is to type “Int” then hit the enter key. Instead of error-ing out, the interpreter does a great job of interpreting a crash test car hitting a cement wall (I had to restart the whole thing.) When I tried the same “technique” in the Python interpreter, I got as a response and for Haskell's interpreter I received “Not in scope: data constructor `Int'”. I also found Scala's function composition to be a little lacking when compared to Haskell. I wasn't able to cleanly change the BigInt data type to String, and then only print out ten characters without requiring three separate val's. Yes, I could have used one var instead, but that's beside the point. I will admit it could be my inexperience with the language showing, so if anyone knows a smoother way to do this in Scala please share it in the comments.

All that being said, I do like the way Scala is trying to handle the reducing of Java's dot notation, and I think it's starting to make strides in the right direction in other areas. I'm open to working with Scala more, and look forward to seeing how it evolves over the next few years.

### I think print has been backported to Python 2 already.

So you might not need the import.

### the "from __future__ import

the "from __future__ import print_function" is needed to use the backport.
If the import was not used, he would have use the print *statement* like this :
print  str(number)[0:10]  #Note the lack of parenthesis.

### Nope, you don't need the "from __future__ import print_function"

If you put parenthesis around what you want to print, python 2.x treats it as a print statement with one value, and python 3.x treats it as a function call with one parameter.

I tested it, and it works without the __future__ import in python 2.4 -> 3.3 inclusive.

### Also, also (sorry to keep

Also, also (sorry to keep spamming :-) are you using a recent version of scala? When I type "Int" into my interpreter, I get:

scala> Int
res0: Int.type = object scala.Int

### No worries about the spam. I

No worries about the spam. I believe I was using 2.8.2 in Fedora 16. I'm glad that they fixed that bug! Thank you for sharing.

### And what is wrong with:

And what is wrong with:

1. val sums = big_number.sum.toString.take(10)

In general, scala does some really clever stuff, but if you try to write it like java, you will miss all of the interesting bits.

### Thank you for answering my

Thank you for answering my question about how to reduce my code. I knew there was a way to do it, but I couldn't figure it out with the space syntax. I was trying to do things like this:

x sum toString take 10

and that wasn't working I was getting this error:

<console>:10: error: type mismatch;
found : java.lang.String
required: Numeric[?]

x sum toString take 10
^

Am I trying to use the space notation in a way that was not inteded?

### Parsing is done before

Parsing is done before typing, so (x sum toString) must be parsed in exactly the same way as (x take 10) or (2 + 2).
That means x.sum(toString). If you want x.sum.toString you need to say so.

### Thank you for the

Thank you for the explanation. I guess I thinking more like Haskell and less like Scala then. I will remember this in for the future.

### Your scala code is slower

Your scala code is slower because you are doing a bunch more work! You are creating a list of Strings, and then mapping a function over that list to make a list of BigInts. That mapping isn't free.

If you want to have the _same_ code in all three languages, then the list creation would look like:

1. val big_number = List(BigInt("37107287533902102798797998220837590246510135740250"), ...

### I think Scala has such bad

I think Scala has such bad times because you're including JVM startup time, which is notoriously long.

Scala should beat Python by tons after warming up the JVM.

### Hi Lucian, thank you for the

Hi Lucian, thank you for the comment. I completely agree, Java generally does execute faster than Python and that even includes the start up time. That is why the results were so shocking. As Andrew talked about above, my process could be optimized a bit. I'm not sure how much it would help, but I'm willing to spend the time modifing the code to expirement.

### But can you do it faster?

Can you do it without using big ints? It is possible to do it without calculating the whole sum but just calculating the first 100 digits!

### What if the numbers were 100,000 digits long?

Project Euler is about algorithms, not just code. If your solution doesn't scale, you're likely to have to find one that does for some other, later problem. The prime number problems show this the best; see

http://stackoverflow.com/questions/6789649/how-can-i-get-this-python-code-to-run-more-quickly-project-euler-problem-7

and my answer to it for an example.

Since you know how many digits you need in the output and you know how many numbers you are adding, you can calculate how many digits you need to consider in the input to get the output digits.

Look at the case of adding two four digit numbers, where you need two digits to be correct. Assume the numbers are of the same magnitude (as in the test data) or left-padded with zeros.

If you consider two digits of each input number, then at worst case you're ignoring a 99 at the end of each number. 99 * 2 = 198, so your second digit could be wrong because of a carried digit you're ignoring.

If you consider three digits of each input number, then at worst case you're ignoring a 9 at the end of each number. 9 * 2 = 18, so the second digit of your answer can't be affected by the ignored digit -- only the third digit of your answer could be affected, and you only need two digits.

So for 2-10 numbers, one digit more than the output length is sufficient (since any number * 10 will carry over only one digit).
For 11-100 numbers, two digits more than the output length are sufficient (since any number * 100 will carry over only two digits).

The algorithm for determining how many extra digits you need should be clear. In Python, it can be written as:

int(math.ceil(math.log10(number_of_input_numbers)))

If you rewrite your code to use that algorithm -- and maybe load the numbers from an external file for the sake of your post length :) -- it will be a much more interesting problem.

### Agf, Thank you for sharing

Agf,

Thank you for sharing with me the "inner" thoughs of project euler. I've always thought it more as coding exercises than algorithm excersices. Sadly algo's has never been my strongest suit. Are there materials that I could read, preferably in book form, that would help me understand more of these "math" algorithms? I ask because I would never have guessed that I could reduce the size of each number to speed up computation; like you explained above.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.