|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 13: Large Sum |
|
3
|
|
|
=================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem13 |
|
6
|
|
|
:synopsis: My solution to problem #13. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem13.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. |
|
15
|
|
|
|
|
16
|
|
|
.. math:: |
|
17
|
|
|
|
|
18
|
|
|
37107287533902102798797998220837590246510135740250 \\\\ |
|
19
|
|
|
46376937677490009712648124896970078050417018260538 \\\\ |
|
20
|
|
|
74324986199524741059474233309513058123726617309629 \\\\ |
|
21
|
|
|
91942213363574161572522430563301811072406154908250 \\\\ |
|
22
|
|
|
23067588207539346171171980310421047513778063246676 \\\\ |
|
23
|
|
|
89261670696623633820136378418383684178734361726757 \\\\ |
|
24
|
|
|
28112879812849979408065481931592621691275889832738 \\\\ |
|
25
|
|
|
44274228917432520321923589422876796487670272189318 \\\\ |
|
26
|
|
|
47451445736001306439091167216856844588711603153276 \\\\ |
|
27
|
|
|
70386486105843025439939619828917593665686757934951 \\\\ |
|
28
|
|
|
62176457141856560629502157223196586755079324193331 \\\\ |
|
29
|
|
|
64906352462741904929101432445813822663347944758178 \\\\ |
|
30
|
|
|
92575867718337217661963751590579239728245598838407 \\\\ |
|
31
|
|
|
58203565325359399008402633568948830189458628227828 \\\\ |
|
32
|
|
|
80181199384826282014278194139940567587151170094390 \\\\ |
|
33
|
|
|
35398664372827112653829987240784473053190104293586 \\\\ |
|
34
|
|
|
86515506006295864861532075273371959191420517255829 \\\\ |
|
35
|
|
|
71693888707715466499115593487603532921714970056938 \\\\ |
|
36
|
|
|
54370070576826684624621495650076471787294438377604 \\\\ |
|
37
|
|
|
53282654108756828443191190634694037855217779295145 \\\\ |
|
38
|
|
|
36123272525000296071075082563815656710885258350721 \\\\ |
|
39
|
|
|
45876576172410976447339110607218265236877223636045 \\\\ |
|
40
|
|
|
17423706905851860660448207621209813287860733969412 \\\\ |
|
41
|
|
|
81142660418086830619328460811191061556940512689692 \\\\ |
|
42
|
|
|
51934325451728388641918047049293215058642563049483 \\\\ |
|
43
|
|
|
62467221648435076201727918039944693004732956340691 \\\\ |
|
44
|
|
|
15732444386908125794514089057706229429197107928209 \\\\ |
|
45
|
|
|
55037687525678773091862540744969844508330393682126 \\\\ |
|
46
|
|
|
18336384825330154686196124348767681297534375946515 \\\\ |
|
47
|
|
|
80386287592878490201521685554828717201219257766954 \\\\ |
|
48
|
|
|
78182833757993103614740356856449095527097864797581 \\\\ |
|
49
|
|
|
16726320100436897842553539920931837441497806860984 \\\\ |
|
50
|
|
|
48403098129077791799088218795327364475675590848030 \\\\ |
|
51
|
|
|
87086987551392711854517078544161852424320693150332 \\\\ |
|
52
|
|
|
59959406895756536782107074926966537676326235447210 \\\\ |
|
53
|
|
|
69793950679652694742597709739166693763042633987085 \\\\ |
|
54
|
|
|
41052684708299085211399427365734116182760315001271 \\\\ |
|
55
|
|
|
65378607361501080857009149939512557028198746004375 \\\\ |
|
56
|
|
|
35829035317434717326932123578154982629742552737307 \\\\ |
|
57
|
|
|
94953759765105305946966067683156574377167401875275 \\\\ |
|
58
|
|
|
88902802571733229619176668713819931811048770190271 \\\\ |
|
59
|
|
|
25267680276078003013678680992525463401061632866526 \\\\ |
|
60
|
|
|
36270218540497705585629946580636237993140746255962 \\\\ |
|
61
|
|
|
24074486908231174977792365466257246923322810917141 \\\\ |
|
62
|
|
|
91430288197103288597806669760892938638285025333403 \\\\ |
|
63
|
|
|
34413065578016127815921815005561868836468420090470 \\\\ |
|
64
|
|
|
23053081172816430487623791969842487255036638784583 \\\\ |
|
65
|
|
|
11487696932154902810424020138335124462181441773470 \\\\ |
|
66
|
|
|
63783299490636259666498587618221225225512486764533 \\\\ |
|
67
|
|
|
67720186971698544312419572409913959008952310058822 \\\\ |
|
68
|
|
|
95548255300263520781532296796249481641953868218774 \\\\ |
|
69
|
|
|
76085327132285723110424803456124867697064507995236 \\\\ |
|
70
|
|
|
37774242535411291684276865538926205024910326572967 \\\\ |
|
71
|
|
|
23701913275725675285653248258265463092207058596522 \\\\ |
|
72
|
|
|
29798860272258331913126375147341994889534765745501 \\\\ |
|
73
|
|
|
18495701454879288984856827726077713721403798879715 \\\\ |
|
74
|
|
|
38298203783031473527721580348144513491373226651381 \\\\ |
|
75
|
|
|
34829543829199918180278916522431027392251122869539 \\\\ |
|
76
|
|
|
40957953066405232632538044100059654939159879593635 \\\\ |
|
77
|
|
|
29746152185502371307642255121183693803580388584903 \\\\ |
|
78
|
|
|
41698116222072977186158236678424689157993532961922 \\\\ |
|
79
|
|
|
62467957194401269043877107275048102390895523597457 \\\\ |
|
80
|
|
|
23189706772547915061505504953922979530901129967519 \\\\ |
|
81
|
|
|
86188088225875314529584099251203829009407770775672 \\\\ |
|
82
|
|
|
11306739708304724483816533873502340845647058077308 \\\\ |
|
83
|
|
|
82959174767140363198008187129011875491310547126581 \\\\ |
|
84
|
|
|
97623331044818386269515456334926366572897563400500 \\\\ |
|
85
|
|
|
42846280183517070527831839425882145521227251250327 \\\\ |
|
86
|
|
|
55121603546981200581762165212827652751691296897789 \\\\ |
|
87
|
|
|
32238195734329339946437501907836945765883352399886 \\\\ |
|
88
|
|
|
75506164965184775180738168837861091527357929701337 \\\\ |
|
89
|
|
|
62177842752192623401942399639168044983993173312731 \\\\ |
|
90
|
|
|
32924185707147349566916674687634660915035914677504 \\\\ |
|
91
|
|
|
99518671430235219628894890102423325116913619626622 \\\\ |
|
92
|
|
|
73267460800591547471830798392868535206946944540724 \\\\ |
|
93
|
|
|
76841822524674417161514036427982273348055556214818 \\\\ |
|
94
|
|
|
97142617910342598647204516893989422179826088076852 \\\\ |
|
95
|
|
|
87783646182799346313767754307809363333018982642090 \\\\ |
|
96
|
|
|
10848802521674670883215120185883543223812876952786 \\\\ |
|
97
|
|
|
71329612474782464538636993009049310363619763878039 \\\\ |
|
98
|
|
|
62184073572399794223406235393808339651327408011116 \\\\ |
|
99
|
|
|
66627891981488087797941876876144230030984490851411 \\\\ |
|
100
|
|
|
60661826293682836764744779239180335110989069790714 \\\\ |
|
101
|
|
|
85786944089552990653640447425576083659976645795096 \\\\ |
|
102
|
|
|
66024396409905389607120198219976047599490197230297 \\\\ |
|
103
|
|
|
64913982680032973156037120041377903785566085089252 \\\\ |
|
104
|
|
|
16730939319872750275468906903707539413042652315011 \\\\ |
|
105
|
|
|
94809377245048795150954100921645863754710598436791 \\\\ |
|
106
|
|
|
78639167021187492431995700641917969777599028300699 \\\\ |
|
107
|
|
|
15368713711936614952811305876380278410754449733078 \\\\ |
|
108
|
|
|
40789923115535562561142322423255033685442488917353 \\\\ |
|
109
|
|
|
44889911501440648020369068063960672322193204149535 \\\\ |
|
110
|
|
|
41503128880339536053299340368006977710650566631954 \\\\ |
|
111
|
|
|
81234880673210146739058568557934581403627822703280 \\\\ |
|
112
|
|
|
82616570773948327592232845941706525094512325230608 \\\\ |
|
113
|
|
|
22918802058777319719839450180888072429661980811197 \\\\ |
|
114
|
|
|
77158542502016545090413245809786882778948721859617 \\\\ |
|
115
|
|
|
72107838435069186155435662884062257473692284509516 \\\\ |
|
116
|
|
|
20849603980134001723930671666823555245252804609722 \\\\ |
|
117
|
|
|
53503534226472524250874054075591789781264330331690 |
|
118
|
|
|
|
|
119
|
|
|
Solution Discussion |
|
120
|
|
|
################### |
|
121
|
|
|
|
|
122
|
|
|
Simply use Python's arbitrary precision arithmetic to compute this large sum, then divide by the appropriate power of |
|
|
|
|
|
|
123
|
|
|
:math:`10` to leave the :math:`10` most significant digits. |
|
124
|
|
|
|
|
125
|
|
|
Solution Implementation |
|
126
|
|
|
####################### |
|
127
|
|
|
|
|
128
|
|
|
.. literalinclude:: ../../solutions/problem13.py |
|
129
|
|
|
:language: python |
|
130
|
|
|
:lines: 133- |
|
131
|
|
|
""" |
|
132
|
|
|
|
|
133
|
|
|
from lib.digital import num_digits |
|
134
|
|
|
|
|
135
|
|
|
|
|
136
|
|
|
def solve(): |
|
137
|
|
|
""" Compute the answer to Project Euler's problem #13 """ |
|
138
|
|
|
|
|
139
|
|
|
# Build a list of integers |
|
140
|
|
|
numbers = """ |
|
141
|
|
|
37107287533902102798797998220837590246510135740250 |
|
142
|
|
|
46376937677490009712648124896970078050417018260538 |
|
143
|
|
|
74324986199524741059474233309513058123726617309629 |
|
144
|
|
|
91942213363574161572522430563301811072406154908250 |
|
145
|
|
|
23067588207539346171171980310421047513778063246676 |
|
146
|
|
|
89261670696623633820136378418383684178734361726757 |
|
147
|
|
|
28112879812849979408065481931592621691275889832738 |
|
148
|
|
|
44274228917432520321923589422876796487670272189318 |
|
149
|
|
|
47451445736001306439091167216856844588711603153276 |
|
150
|
|
|
70386486105843025439939619828917593665686757934951 |
|
151
|
|
|
62176457141856560629502157223196586755079324193331 |
|
152
|
|
|
64906352462741904929101432445813822663347944758178 |
|
153
|
|
|
92575867718337217661963751590579239728245598838407 |
|
154
|
|
|
58203565325359399008402633568948830189458628227828 |
|
155
|
|
|
80181199384826282014278194139940567587151170094390 |
|
156
|
|
|
35398664372827112653829987240784473053190104293586 |
|
157
|
|
|
86515506006295864861532075273371959191420517255829 |
|
158
|
|
|
71693888707715466499115593487603532921714970056938 |
|
159
|
|
|
54370070576826684624621495650076471787294438377604 |
|
160
|
|
|
53282654108756828443191190634694037855217779295145 |
|
161
|
|
|
36123272525000296071075082563815656710885258350721 |
|
162
|
|
|
45876576172410976447339110607218265236877223636045 |
|
163
|
|
|
17423706905851860660448207621209813287860733969412 |
|
164
|
|
|
81142660418086830619328460811191061556940512689692 |
|
165
|
|
|
51934325451728388641918047049293215058642563049483 |
|
166
|
|
|
62467221648435076201727918039944693004732956340691 |
|
167
|
|
|
15732444386908125794514089057706229429197107928209 |
|
168
|
|
|
55037687525678773091862540744969844508330393682126 |
|
169
|
|
|
18336384825330154686196124348767681297534375946515 |
|
170
|
|
|
80386287592878490201521685554828717201219257766954 |
|
171
|
|
|
78182833757993103614740356856449095527097864797581 |
|
172
|
|
|
16726320100436897842553539920931837441497806860984 |
|
173
|
|
|
48403098129077791799088218795327364475675590848030 |
|
174
|
|
|
87086987551392711854517078544161852424320693150332 |
|
175
|
|
|
59959406895756536782107074926966537676326235447210 |
|
176
|
|
|
69793950679652694742597709739166693763042633987085 |
|
177
|
|
|
41052684708299085211399427365734116182760315001271 |
|
178
|
|
|
65378607361501080857009149939512557028198746004375 |
|
179
|
|
|
35829035317434717326932123578154982629742552737307 |
|
180
|
|
|
94953759765105305946966067683156574377167401875275 |
|
181
|
|
|
88902802571733229619176668713819931811048770190271 |
|
182
|
|
|
25267680276078003013678680992525463401061632866526 |
|
183
|
|
|
36270218540497705585629946580636237993140746255962 |
|
184
|
|
|
24074486908231174977792365466257246923322810917141 |
|
185
|
|
|
91430288197103288597806669760892938638285025333403 |
|
186
|
|
|
34413065578016127815921815005561868836468420090470 |
|
187
|
|
|
23053081172816430487623791969842487255036638784583 |
|
188
|
|
|
11487696932154902810424020138335124462181441773470 |
|
189
|
|
|
63783299490636259666498587618221225225512486764533 |
|
190
|
|
|
67720186971698544312419572409913959008952310058822 |
|
191
|
|
|
95548255300263520781532296796249481641953868218774 |
|
192
|
|
|
76085327132285723110424803456124867697064507995236 |
|
193
|
|
|
37774242535411291684276865538926205024910326572967 |
|
194
|
|
|
23701913275725675285653248258265463092207058596522 |
|
195
|
|
|
29798860272258331913126375147341994889534765745501 |
|
196
|
|
|
18495701454879288984856827726077713721403798879715 |
|
197
|
|
|
38298203783031473527721580348144513491373226651381 |
|
198
|
|
|
34829543829199918180278916522431027392251122869539 |
|
199
|
|
|
40957953066405232632538044100059654939159879593635 |
|
200
|
|
|
29746152185502371307642255121183693803580388584903 |
|
201
|
|
|
41698116222072977186158236678424689157993532961922 |
|
202
|
|
|
62467957194401269043877107275048102390895523597457 |
|
203
|
|
|
23189706772547915061505504953922979530901129967519 |
|
204
|
|
|
86188088225875314529584099251203829009407770775672 |
|
205
|
|
|
11306739708304724483816533873502340845647058077308 |
|
206
|
|
|
82959174767140363198008187129011875491310547126581 |
|
207
|
|
|
97623331044818386269515456334926366572897563400500 |
|
208
|
|
|
42846280183517070527831839425882145521227251250327 |
|
209
|
|
|
55121603546981200581762165212827652751691296897789 |
|
210
|
|
|
32238195734329339946437501907836945765883352399886 |
|
211
|
|
|
75506164965184775180738168837861091527357929701337 |
|
212
|
|
|
62177842752192623401942399639168044983993173312731 |
|
213
|
|
|
32924185707147349566916674687634660915035914677504 |
|
214
|
|
|
99518671430235219628894890102423325116913619626622 |
|
215
|
|
|
73267460800591547471830798392868535206946944540724 |
|
216
|
|
|
76841822524674417161514036427982273348055556214818 |
|
217
|
|
|
97142617910342598647204516893989422179826088076852 |
|
218
|
|
|
87783646182799346313767754307809363333018982642090 |
|
219
|
|
|
10848802521674670883215120185883543223812876952786 |
|
220
|
|
|
71329612474782464538636993009049310363619763878039 |
|
221
|
|
|
62184073572399794223406235393808339651327408011116 |
|
222
|
|
|
66627891981488087797941876876144230030984490851411 |
|
223
|
|
|
60661826293682836764744779239180335110989069790714 |
|
224
|
|
|
85786944089552990653640447425576083659976645795096 |
|
225
|
|
|
66024396409905389607120198219976047599490197230297 |
|
226
|
|
|
64913982680032973156037120041377903785566085089252 |
|
227
|
|
|
16730939319872750275468906903707539413042652315011 |
|
228
|
|
|
94809377245048795150954100921645863754710598436791 |
|
229
|
|
|
78639167021187492431995700641917969777599028300699 |
|
230
|
|
|
15368713711936614952811305876380278410754449733078 |
|
231
|
|
|
40789923115535562561142322423255033685442488917353 |
|
232
|
|
|
44889911501440648020369068063960672322193204149535 |
|
233
|
|
|
41503128880339536053299340368006977710650566631954 |
|
234
|
|
|
81234880673210146739058568557934581403627822703280 |
|
235
|
|
|
82616570773948327592232845941706525094512325230608 |
|
236
|
|
|
22918802058777319719839450180888072429661980811197 |
|
237
|
|
|
77158542502016545090413245809786882778948721859617 |
|
238
|
|
|
72107838435069186155435662884062257473692284509516 |
|
239
|
|
|
20849603980134001723930671666823555245252804609722 |
|
240
|
|
|
53503534226472524250874054075591789781264330331690 |
|
241
|
|
|
""" |
|
242
|
|
|
numbers = numbers.split("\n") |
|
243
|
|
|
numbers = [number.strip() for number in numbers] |
|
244
|
|
|
numbers = [int(number) for number in numbers if number != ""] |
|
245
|
|
|
|
|
246
|
|
|
# Sum the list of integers |
|
247
|
|
|
total = sum(numbers) |
|
248
|
|
|
|
|
249
|
|
|
# Compute the number of digits in the sum, and how many to truncate to give the top 10 digits |
|
250
|
|
|
target = 10 |
|
251
|
|
|
n_digits = num_digits(total) |
|
252
|
|
|
truncate_digits = n_digits - target |
|
253
|
|
|
|
|
254
|
|
|
# Compute the final answer (first 10 digits) |
|
255
|
|
|
answer = total // (10 ** truncate_digits) |
|
256
|
|
|
return answer |
|
257
|
|
|
|
|
258
|
|
|
|
|
259
|
|
|
expected_answer = 5537376230 |
|
|
|
|
|
|
260
|
|
|
|
Bill
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.