# Project Euler 13: Sum of 50-digit numbers

There is nothing particularly mathematically interesting in Problem 13 of Project Euler.  Since the question is about summing numbers. The tricky part of the question is that the numbers are so big they don’t fit into an ordinary data type. The question goes

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

I have left out the actual numbers, but check the question for them.  I originally solved the question using arrays of integers to store each number in, and then I thought I was very smug and all. But when I sought a bit of inspiration on the internet before writing this blog post, I realised that many other languages has built in support for large integers.

## Solution

It turns out that from .NET4.0 there is support for big integers as well. In C# this support is called something as surprisingly as System.Diagnostics.BigInteger. Using this class makes the question trivial.  It feels a bit like cheating, but on the other hand it is probably the most effective way to solve the problem.

I chose to store the input numbers in a file, and used the following piece of code to get the answer

```string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";

BigInteger result = new BigInteger();
string line;

while ((line = r.ReadLine()) != null) {
result += BigInteger.Parse(line);
}

r.Close();
```

And the result

```The first ten digits are: 5537376230
Solution took 5 ms
```

The only thing I found slightly hard is that the .net component called System.Numerics is not included per default in Visual Studio Express. So you have to add a reference to the library. Apart from that it is very easy.

## Source code

### Posted by Kristian

Sasa

This is a very elegant solution.

Respect.

Kristian

I think the short answer to that is thank you 🙂

Guy David

This is a pretty nice code.

Please correct me if I’m wrong, and I’m pretty sure my code is only faster since I made a string out of all the numbers together, instead of reading a file.

On my slow PC it gave a result of 2 ms:

```Stopwatch c = Stopwatch.StartNew();

string a = "37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854370070576826684624621495650076471787294438377604532826541087568284431911906346940378552177792951453612327252500029607107508256381565671088525835072145876576172410976447339110607218265236877223636045174237069058518606604482076212098132878607339694128114266041808683061932846081119106155694051268969251934325451728388641918047049293215058642563049483624672216484350762017279180399446930047329563406911573244438690812579451408905770622942919710792820955037687525678773091862540744969844508330393682126183363848253301546861961243487676812975343759465158038628759287849020152168555482871720121925776695478182833757993103614740356856449095527097864797581167263201004368978425535399209318374414978068609844840309812907779179908821879532736447567559084803087086987551392711854517078544161852424320693150332599594068957565367821070749269665376763262354472106979395067965269474259770973916669376304263398708541052684708299085211399427365734116182760315001271653786073615010808570091499395125570281987460043753582903531743471732693212357815498262974255273730794953759765105305946966067683156574377167401875275889028025717332296191766687138199318110487701902712526768027607800301367868099252546340106163286652636270218540497705585629946580636237993140746255962240744869082311749777923654662572469233228109171419143028819710328859780666976089293863828502533340334413065578016127815921815005561868836468420090470230530811728164304876237919698424872550366387845831148769693215490281042402013833512446218144177347063783299490636259666498587618221225225512486764533677201869716985443124195724099139590089523100588229554825530026352078153229679624948164195386821877476085327132285723110424803456124867697064507995236377742425354112916842768655389262050249103265729672370191327572567528565324825826546309220705859652229798860272258331913126375147341994889534765745501184957014548792889848568277260777137214037988797153829820378303147352772158034814451349137322665138134829543829199918180278916522431027392251122869539409579530664052326325380441000596549391598795936352974615218550237130764225512118369380358038858490341698116222072977186158236678424689157993532961922624679571944012690438771072750481023908955235974572318970677254791506150550495392297953090112996751986188088225875314529584099251203829009407770775672113067397083047244838165338735023408456470580773088295917476714036319800818712901187549131054712658197623331044818386269515456334926366572897563400500428462801835170705278318394258821455212272512503275512160354698120058176216521282765275169129689778932238195734329339946437501907836945765883352399886755061649651847751807381688378610915273579297013376217784275219262340194239963916804498399317331273132924185707147349566916674687634660915035914677504995186714302352196288948901024233251169136196266227326746080059154747183079839286853520694694454072476841822524674417161514036427982273348055556214818971426179103425986472045168939894221798260880768528778364618279934631376775430780936333301898264209010848802521674670883215120185883543223812876952786713296124747824645386369930090493103636197638780396218407357239979422340623539380833965132740801111666627891981488087797941876876144230030984490851411606618262936828367647447792391803351109890697907148578694408955299065364044742557608365997664579509666024396409905389607120198219976047599490197230297649139826800329731560371200413779037855660850892521673093931987275027546890690370753941304265231501194809377245048795150954100921645863754710598436791786391670211874924319957006419179697775990283006991536871371193661495281130587638027841075444973307840789923115535562561142322423255033685442488917353448899115014406480203690680639606723221932041495354150312888033953605329934036800697771065056663195481234880673210146739058568557934581403627822703280826165707739483275922328459417065250945123252306082291880205877731971983945018088807242966198081119777158542502016545090413245809786882778948721859617721078384350691861554356628840622574736922845095162084960398013400172393067166682355524525280460972253503534226472524250874054075591789781264330331690";

BigInteger max = 0;

for (int i = 0; i < 100; i++)
{
max += BigInteger.Parse(a.Substring(i * 50, 50));
}

string b = max.ToString().Substring(0, 10);

c.Stop();
Console.WriteLine("The solution took {0} ms", c.ElapsedMilliseconds);
Console.WriteLine("The answer is " + b);
```
Kristian

Without having run your code, you are most likely right. Using filesystem operations is always slow. So converting it all to a string is going to speed things up. And for a problem like this, using a string is fine.

/Kristian

saveen

//in c#

using System;

namespace Console_large_sum_challenge
{
class Program
{
static void Main(string[] args)
{
string largenumber=”37107287533902102798797998220837590246510135740250″+
“46376937677490009712648124896970078050417018260538”+
“74324986199524741059474233309513058123726617309629”+
“91942213363574161572522430563301811072406154908250”+
“23067588207539346171171980310421047513778063246676”+
“89261670696623633820136378418383684178734361726757”+
“28112879812849979408065481931592621691275889832738”+
“44274228917432520321923589422876796487670272189318”+
“47451445736001306439091167216856844588711603153276”+
“70386486105843025439939619828917593665686757934951”+
“62176457141856560629502157223196586755079324193331”+
“64906352462741904929101432445813822663347944758178”+
“92575867718337217661963751590579239728245598838407”+
“58203565325359399008402633568948830189458628227828”+
“80181199384826282014278194139940567587151170094390”+
“35398664372827112653829987240784473053190104293586”+
“86515506006295864861532075273371959191420517255829”+
“71693888707715466499115593487603532921714970056938”+
“54370070576826684624621495650076471787294438377604”+
“53282654108756828443191190634694037855217779295145”+
“36123272525000296071075082563815656710885258350721”+
“45876576172410976447339110607218265236877223636045”+
“17423706905851860660448207621209813287860733969412”+
“81142660418086830619328460811191061556940512689692”+
“51934325451728388641918047049293215058642563049483”+
“62467221648435076201727918039944693004732956340691”+
“15732444386908125794514089057706229429197107928209”+
“55037687525678773091862540744969844508330393682126”+
“18336384825330154686196124348767681297534375946515”+
“80386287592878490201521685554828717201219257766954”+
“78182833757993103614740356856449095527097864797581”+
“16726320100436897842553539920931837441497806860984”+
“48403098129077791799088218795327364475675590848030”+
“87086987551392711854517078544161852424320693150332”+
“59959406895756536782107074926966537676326235447210”+
“69793950679652694742597709739166693763042633987085”+
“41052684708299085211399427365734116182760315001271”+
“65378607361501080857009149939512557028198746004375”+
“35829035317434717326932123578154982629742552737307”+
“94953759765105305946966067683156574377167401875275”+
“88902802571733229619176668713819931811048770190271”+
“25267680276078003013678680992525463401061632866526”+
“36270218540497705585629946580636237993140746255962”+
“24074486908231174977792365466257246923322810917141”+
“91430288197103288597806669760892938638285025333403”+
“34413065578016127815921815005561868836468420090470”+
“23053081172816430487623791969842487255036638784583”+
“11487696932154902810424020138335124462181441773470”+
“63783299490636259666498587618221225225512486764533”+
“67720186971698544312419572409913959008952310058822”+
“95548255300263520781532296796249481641953868218774”+
“76085327132285723110424803456124867697064507995236”+
“37774242535411291684276865538926205024910326572967”+
“23701913275725675285653248258265463092207058596522”+
“29798860272258331913126375147341994889534765745501”+
“18495701454879288984856827726077713721403798879715”+
“38298203783031473527721580348144513491373226651381”+
“34829543829199918180278916522431027392251122869539”+
“40957953066405232632538044100059654939159879593635”+
“29746152185502371307642255121183693803580388584903”+
“41698116222072977186158236678424689157993532961922”+
“62467957194401269043877107275048102390895523597457”+
“23189706772547915061505504953922979530901129967519”+
“86188088225875314529584099251203829009407770775672”+
“11306739708304724483816533873502340845647058077308”+
“82959174767140363198008187129011875491310547126581”+
“97623331044818386269515456334926366572897563400500”+
“42846280183517070527831839425882145521227251250327”+
“55121603546981200581762165212827652751691296897789”+
“32238195734329339946437501907836945765883352399886”+
“75506164965184775180738168837861091527357929701337”+
“62177842752192623401942399639168044983993173312731”+
“32924185707147349566916674687634660915035914677504”+
“99518671430235219628894890102423325116913619626622”+
“73267460800591547471830798392868535206946944540724”+
“76841822524674417161514036427982273348055556214818”+
“97142617910342598647204516893989422179826088076852”+
“87783646182799346313767754307809363333018982642090”+
“10848802521674670883215120185883543223812876952786”+
“71329612474782464538636993009049310363619763878039”+
“62184073572399794223406235393808339651327408011116”+
“66627891981488087797941876876144230030984490851411”+
“60661826293682836764744779239180335110989069790714”+
“85786944089552990653640447425576083659976645795096”+
“66024396409905389607120198219976047599490197230297”+
“64913982680032973156037120041377903785566085089252”+
“16730939319872750275468906903707539413042652315011”+
“94809377245048795150954100921645863754710598436791”+
“78639167021187492431995700641917969777599028300699”+
“15368713711936614952811305876380278410754449733078”+
“40789923115535562561142322423255033685442488917353”+
“44889911501440648020369068063960672322193204149535”+
“41503128880339536053299340368006977710650566631954”+
“81234880673210146739058568557934581403627822703280”+
“82616570773948327592232845941706525094512325230608”+
“22918802058777319719839450180888072429661980811197”+
“77158542502016545090413245809786882778948721859617”+
“72107838435069186155435662884062257473692284509516”+
“20849603980134001723930671666823555245252804609722”+
“53503534226472524250874054075591789781264330331690”;
double sum = 0;
string extract;
int[] array = new int[50];
int[] array2 = new int[51];
int count = 0,to=0,k=0,carry=0,carry2=0;
for (int i = 0; i < 100; i++)
{
for (int j =count ; j = 0; p–, l–)
{
if (p 9)
{

array2[l] = (temp % 10) + carry;
carry = temp / 10;

}
else
{

array2[l] = temp + carry;
carry = 0;

}
}
}
carry = 0;

}

for (int j = 0; j < 9; j++)
{
Console.Write(array2[j]);
}

}
}
}

vincian

#!/bin/bash
a=0;
for i in \$(cat temp)
do
a=`echo \$a+\$i | bc`
done
echo \$a

just copy all those no.s to “temp” file as it is..

vincian

instead of echo \$a… do echo \${a:0:10} for 10 digits only 😉

Sidhant

//Beautiful

#include
using namespace std;
int main(){
int no[100][50];
int finale[53];
string tot=”37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854370070576826684624621495650076471787294438377604532826541087568284431911906346940378552177792951453612327252500029607107508256381565671088525835072145876576172410976447339110607218265236877223636045174237069058518606604482076212098132878607339694128114266041808683061932846081119106155694051268969251934325451728388641918047049293215058642563049483624672216484350762017279180399446930047329563406911573244438690812579451408905770622942919710792820955037687525678773091862540744969844508330393682126183363848253301546861961243487676812975343759465158038628759287849020152168555482871720121925776695478182833757993103614740356856449095527097864797581167263201004368978425535399209318374414978068609844840309812907779179908821879532736447567559084803087086987551392711854517078544161852424320693150332599594068957565367821070749269665376763262354472106979395067965269474259770973916669376304263398708541052684708299085211399427365734116182760315001271653786073615010808570091499395125570281987460043753582903531743471732693212357815498262974255273730794953759765105305946966067683156574377167401875275889028025717332296191766687138199318110487701902712526768027607800301367868099252546340106163286652636270218540497705585629946580636237993140746255962240744869082311749777923654662572469233228109171419143028819710328859780666976089293863828502533340334413065578016127815921815005561868836468420090470230530811728164304876237919698424872550366387845831148769693215490281042402013833512446218144177347063783299490636259666498587618221225225512486764533677201869716985443124195724099139590089523100588229554825530026352078153229679624948164195386821877476085327132285723110424803456124867697064507995236377742425354112916842768655389262050249103265729672370191327572567528565324825826546309220705859652229798860272258331913126375147341994889534765745501184957014548792889848568277260777137214037988797153829820378303147352772158034814451349137322665138134829543829199918180278916522431027392251122869539409579530664052326325380441000596549391598795936352974615218550237130764225512118369380358038858490341698116222072977186158236678424689157993532961922624679571944012690438771072750481023908955235974572318970677254791506150550495392297953090112996751986188088225875314529584099251203829009407770775672113067397083047244838165338735023408456470580773088295917476714036319800818712901187549131054712658197623331044818386269515456334926366572897563400500428462801835170705278318394258821455212272512503275512160354698120058176216521282765275169129689778932238195734329339946437501907836945765883352399886755061649651847751807381688378610915273579297013376217784275219262340194239963916804498399317331273132924185707147349566916674687634660915035914677504995186714302352196288948901024233251169136196266227326746080059154747183079839286853520694694454072476841822524674417161514036427982273348055556214818971426179103425986472045168939894221798260880768528778364618279934631376775430780936333301898264209010848802521674670883215120185883543223812876952786713296124747824645386369930090493103636197638780396218407357239979422340623539380833965132740801111666627891981488087797941876876144230030984490851411606618262936828367647447792391803351109890697907148578694408955299065364044742557608365997664579509666024396409905389607120198219976047599490197230297649139826800329731560371200413779037855660850892521673093931987275027546890690370753941304265231501194809377245048795150954100921645863754710598436791786391670211874924319957006419179697775990283006991536871371193661495281130587638027841075444973307840789923115535562561142322423255033685442488917353448899115014406480203690680639606723221932041495354150312888033953605329934036800697771065056663195481234880673210146739058568557934581403627822703280826165707739483275922328459417065250945123252306082291880205877731971983945018088807242966198081119777158542502016545090413245809786882778948721859617721078384350691861554356628840622574736922845095162084960398013400172393067166682355524525280460972253503534226472524250874054075591789781264330331690″;
for(int i=0;i<=99;i++){
for(int j=0;j<=49;j++){
temp=tot[counter]-48;
no[i][j]=temp;
//cout<<no[i][j];
counter++;
}
//cout<=0;i–){
for(int j=0;j<=99;j++){
//cout<<no[j][i]<<"\n";
//cout<<"Carry="<<carry<<"\n";
//cout<<normal;
}
cout<<"Normal="<<normal<<"\n";
cout<<"CARRY="<<carry<<"\n";
}
//cout<<no[0][50];
cin.get();
}

Sidhant

#include
using namespace std;
int main(){
int no[100][50];
int finale[53];
string tot=”37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854370070576826684624621495650076471787294438377604532826541087568284431911906346940378552177792951453612327252500029607107508256381565671088525835072145876576172410976447339110607218265236877223636045174237069058518606604482076212098132878607339694128114266041808683061932846081119106155694051268969251934325451728388641918047049293215058642563049483624672216484350762017279180399446930047329563406911573244438690812579451408905770622942919710792820955037687525678773091862540744969844508330393682126183363848253301546861961243487676812975343759465158038628759287849020152168555482871720121925776695478182833757993103614740356856449095527097864797581167263201004368978425535399209318374414978068609844840309812907779179908821879532736447567559084803087086987551392711854517078544161852424320693150332599594068957565367821070749269665376763262354472106979395067965269474259770973916669376304263398708541052684708299085211399427365734116182760315001271653786073615010808570091499395125570281987460043753582903531743471732693212357815498262974255273730794953759765105305946966067683156574377167401875275889028025717332296191766687138199318110487701902712526768027607800301367868099252546340106163286652636270218540497705585629946580636237993140746255962240744869082311749777923654662572469233228109171419143028819710328859780666976089293863828502533340334413065578016127815921815005561868836468420090470230530811728164304876237919698424872550366387845831148769693215490281042402013833512446218144177347063783299490636259666498587618221225225512486764533677201869716985443124195724099139590089523100588229554825530026352078153229679624948164195386821877476085327132285723110424803456124867697064507995236377742425354112916842768655389262050249103265729672370191327572567528565324825826546309220705859652229798860272258331913126375147341994889534765745501184957014548792889848568277260777137214037988797153829820378303147352772158034814451349137322665138134829543829199918180278916522431027392251122869539409579530664052326325380441000596549391598795936352974615218550237130764225512118369380358038858490341698116222072977186158236678424689157993532961922624679571944012690438771072750481023908955235974572318970677254791506150550495392297953090112996751986188088225875314529584099251203829009407770775672113067397083047244838165338735023408456470580773088295917476714036319800818712901187549131054712658197623331044818386269515456334926366572897563400500428462801835170705278318394258821455212272512503275512160354698120058176216521282765275169129689778932238195734329339946437501907836945765883352399886755061649651847751807381688378610915273579297013376217784275219262340194239963916804498399317331273132924185707147349566916674687634660915035914677504995186714302352196288948901024233251169136196266227326746080059154747183079839286853520694694454072476841822524674417161514036427982273348055556214818971426179103425986472045168939894221798260880768528778364618279934631376775430780936333301898264209010848802521674670883215120185883543223812876952786713296124747824645386369930090493103636197638780396218407357239979422340623539380833965132740801111666627891981488087797941876876144230030984490851411606618262936828367647447792391803351109890697907148578694408955299065364044742557608365997664579509666024396409905389607120198219976047599490197230297649139826800329731560371200413779037855660850892521673093931987275027546890690370753941304265231501194809377245048795150954100921645863754710598436791786391670211874924319957006419179697775990283006991536871371193661495281130587638027841075444973307840789923115535562561142322423255033685442488917353448899115014406480203690680639606723221932041495354150312888033953605329934036800697771065056663195481234880673210146739058568557934581403627822703280826165707739483275922328459417065250945123252306082291880205877731971983945018088807242966198081119777158542502016545090413245809786882778948721859617721078384350691861554356628840622574736922845095162084960398013400172393067166682355524525280460972253503534226472524250874054075591789781264330331690″;
for(int i=0;i<=99;i++){
for(int j=0;j<=49;j++){
temp=tot[counter]-48;
no[i][j]=temp;
//cout<<no[i][j];
counter++;
}
//cout<=0;i–){
for(int j=0;j<=99;j++){
//cout<<no[j][i]<<"\n";
//cout<<"Carry="<<carry<<"\n";
//cout<<normal;
}
cout<<"Normal="<<normal<<"\n";
cout<<"CARRY="<<carry<<"\n";
}
//cout<<no[0][50];
cin.get();
}

Gabe

I think the whole idea is that in order to get the 10 most significant digits you don’t need to add the entire number, just taking the first 11 or 12 character (number) from the string, and adding those will give you the correct answer, also it is much faster and conveniently fit in type Long.. at least in Java. here is my example with both solutions.

package ProjectEuler;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.math.BigInteger;

public class LargeSum {
public static void main(String[] args) throws FileNotFoundException {
try {
BigInteger largeNum;
BigInteger sum = BigInteger.valueOf(0);
long largeNumLong = 0L;
long sumLong = 0L;

while(line != null){
// big integer sum
largeNum = new BigInteger(line);
System.out.print(sum + ” “);

// long sum
largeNumLong = Long.parseLong(line.substring(0, 12));
sumLong += largeNumLong;
System.out.print(sumLong);

System.out.println();
}

} catch(IOException e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch(IOException e) {
e.printStackTrace();
}
}

}

}

Kristian

You are right. Given that we have 100 numbers we need to add and they can carry over at most one each, that gives us a maximum carry over of 99. So if we calculate the first 13 digits then we should be sure that we don’t get a rounding error.

Michael

@Kristian only way to be 100% certain that your answer is correct is to do the whole numbers. If, for example, you add up 8999…999 and 1000…001 (Assuming they are both 50 digit numbers) would yield 999…999 (13 digits) if you take the first 13 from each number. This, however, is not a very common case, but it is a case nevertheless.

Kristian

Ouch, you are absolutely right. I forgot that brilliant example.

Diego

Someone knows why this solution in JavaScript doesn’t give me the correct answer?

/**
* Work out the first ten digits of the sum of the following one-hundred
* 50-digit numbers.
*
* The 50-digit numbers are on problem13.txt.
*/

var PROG = PROG || (function() {

var fs = require(‘fs’),
// BigInteger Module
bigInt = require(‘big-integer’),

input : fs.createReadStream( __dirname + ‘/problem13.txt’ ),
output : process.stdout,
terminal : false
});

var bigArray = [], count = 0;

rd.on(‘line’, function( line ) {
bigArray[count] = line;
count += 1;
if ( count === 99 ) {
bigArray[count] = line;
}
});

/**
* Metodo principal da aplicação, retorna os dez primeiros digitos da soma
* de todos os elementos do array BigArray.
*
* @method init
* @return sum 10 primeiros digitos da soma
*/
this.init = function() {
var sum = bigInt();
for ( i = 0 ; i < bigArray.length ; i += 1 ) {
}
return sum.toString().substr(0,10); // Wrong Answer! 5504722300, took 8ms
//return bigArray.length;
};

return this;
}());

setTimeout(function() {
with(console) {
var start = new Date().getTime();
//Variavel marcadora do tempo de execução
var elapsed = new Date().getTime() – start;
log("===================");
log("Took : " + elapsed + "ms");
}
},10);

Noah

I didn’t even think about using BigInt, being new to C#, I was going through these problems to help enhance my skills. At first I took the route of creating an array of 100 “50-digit” strings. Then sent them to a function which looped through each digit beginning from the end and summed one digit at a time (with carries). Then I realized, why limit myself to one digit? So I revamped my solution to the follwoing code.

Note: This works, but of course it’s still open to optimization. For example: After reading through the comments, it could be optimized using the conversation piece between @Gabe, @Kristian, and @Michael.

Average runtime on consecutive runs = 1-2 ms. (5 ms on first run)

```const int Size = 100;
String[] number = new String[Size];

{
DateTime startTime = DateTime.Now;

string path = @"TextFiles\Problem_13.txt";

{
for (int i = 0; i < Size; i++)
}

for (int i = 2; i < Size; i++)

DateTime stopTime = DateTime.Now;
TimeSpan duration = stopTime - startTime;
Console.WriteLine("The first ten digits of the sum are: {0}.", sum.Substring(0, 10));
Console.WriteLine("Solution took {0} ms by Mine", duration.TotalMilliseconds);
}

private String AddLrgInt(String first, String second)
{
String sum = "";

// Ensure the two numbers are the same length for easy work later.
// Note: Optimize this for cases where number lengths differ greatly.
while (first.Length > second.Length)
second = "0" + second;
while (first.Length < second.Length)
first = "0" + first;

int available = first.Length;
ulong carry = 0;

// Sum the last 18 digits of each number.
// Then the next 18 digits plus carry.
// Cont. until all digits summed.
while (available > 0)
{
// Using ulong, the max sum w/o error we can store = 19 digits.
int use = Math.Min(available, 18);

// Get temp sum.
ulong temp = Convert.ToUInt64(first.Substring(available - use, use)) + Convert.ToUInt64(second.Substring(available - use, use)) + carry;
String sTemp = temp.ToString();

while (sTemp.Length < use)
sTemp = "0" + sTemp;

carry = temp / 1000000000000000000;

if (sTemp.Length > 18)
sum = sTemp.Substring(1, sTemp.Length - 1) + sum;
else
sum = sTemp + sum;

available -= use;
}

return sum;
}
```
Noah

Edit: I had another class running as the index so I had to actually call this problem’s Run method as an instance in the index class’ main method. In putting the code on here, I simply made this Run method the main method, but did so incorrectly. Should read:

`static void Main(string[] args){}`

and,

`private static String AddLrgInt(String first, String second){}`
Govind

I obviously didnt think about BigInt. Here is my solution using string.

``` using System; using System.Text; using System.IO;```

``` namespace ClientConsole { class Program { static void Main(string[] args) { string[] strArray = new string[100]; int i = 0, sum = 0; string strSum = ""; string strTemp; //All the numbers are stored in Euler13.txt file using (StreamReader reader = new StreamReader("C:\\Euler13.txt")) { while (!reader.EndOfStream) { //get all numbers in an array of string strArray[i] = reader.ReadLine(); i++; } } ```

``` for (i = 0; i <= 49; i++) { for (int j = 0; j < 100; j++) { //Get the sum of last digits of each number strTemp = strArray[j]; sum = sum + int.Parse(strTemp.Substring(strTemp.Length - 1)); //Remove the last digit from the number strArray[j] = strTemp.Substring(0, strTemp.Length - 1); } strTemp = sum.ToString(); //Add the last digit of the sum to the front of the main string strSum strSum = strTemp.Substring(strTemp.Length - 1) + strSum; //remainder sum = int.Parse(strTemp.Substring(0, strTemp.Length - 1)); } //In the end add the remainder in front of the string strSum = sum.ToString() + strSum; Console.WriteLine("Your result is: "+ strSum.Substring(0, 10)); Console.ReadLine(); } } } ```

Jean-Marie Hachey

Just a note.
No prime numbers were found in the list of one-hundred 50-digit numbers of Project Euler – Problem 13 :
http://projecteuler.net/index.php?section=problems&id=013
The sum:
5 537 376 230 390 876 637 302 048 746 832 985 971 773 659 831 892 672;
(52 digits)
is obviously not a prime either.

Smallest and biggest 50-digit prime numbers :
10000000000000000000000000000000000000000000000009
99999999999999999999999999999999999999999999999943
___

Sources:
1) PE13, Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem13.cs
2) Microsoft Visual C# 2010 Express
3) Java calculator
http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
4) Microsoft Office Excel (2007)

kazititu

to solve this problem I have used regular expression to separate every 50 digit number and after simply adding them…Dont know if it is a good method

package eulerproblem13;

import java.io.Console;
import java.math.*;

public class EulerProblem13 {

public static void main(String[] args) {
BigInteger sum=BigInteger.ZERO ;

String s= “37107287533902102798797998220837590246510135740250”+
“46376937677490009712648124896970078050417018260538”+
“74324986199524741059474233309513058123726617309629”+
“91942213363574161572522430563301811072406154908250”+
“23067588207539346171171980310421047513778063246676”+
“89261670696623633820136378418383684178734361726757”+
“28112879812849979408065481931592621691275889832738”+
“44274228917432520321923589422876796487670272189318”+
“47451445736001306439091167216856844588711603153276”+
“70386486105843025439939619828917593665686757934951”+
“62176457141856560629502157223196586755079324193331”+
“64906352462741904929101432445813822663347944758178”+
“92575867718337217661963751590579239728245598838407”+
“58203565325359399008402633568948830189458628227828”+
“80181199384826282014278194139940567587151170094390”+
“35398664372827112653829987240784473053190104293586”+
“86515506006295864861532075273371959191420517255829”+
“71693888707715466499115593487603532921714970056938”+
“54370070576826684624621495650076471787294438377604”+
“53282654108756828443191190634694037855217779295145”+
“36123272525000296071075082563815656710885258350721”+
“45876576172410976447339110607218265236877223636045”+
“17423706905851860660448207621209813287860733969412”+
“81142660418086830619328460811191061556940512689692”+
“51934325451728388641918047049293215058642563049483”+
“62467221648435076201727918039944693004732956340691”+
“15732444386908125794514089057706229429197107928209”+
“55037687525678773091862540744969844508330393682126”+
“18336384825330154686196124348767681297534375946515”+
“80386287592878490201521685554828717201219257766954”+
“78182833757993103614740356856449095527097864797581”+
“16726320100436897842553539920931837441497806860984”+
“48403098129077791799088218795327364475675590848030”+
“87086987551392711854517078544161852424320693150332”+
“59959406895756536782107074926966537676326235447210”+
“69793950679652694742597709739166693763042633987085”+
“41052684708299085211399427365734116182760315001271”+
“65378607361501080857009149939512557028198746004375”+
“35829035317434717326932123578154982629742552737307”+
“94953759765105305946966067683156574377167401875275”+
“88902802571733229619176668713819931811048770190271”+
“25267680276078003013678680992525463401061632866526”+
“36270218540497705585629946580636237993140746255962”+
“24074486908231174977792365466257246923322810917141”+
“91430288197103288597806669760892938638285025333403”+
“34413065578016127815921815005561868836468420090470”+
“23053081172816430487623791969842487255036638784583”+
“11487696932154902810424020138335124462181441773470”+
“63783299490636259666498587618221225225512486764533”+
“67720186971698544312419572409913959008952310058822”+
“95548255300263520781532296796249481641953868218774”+
“76085327132285723110424803456124867697064507995236”+
“37774242535411291684276865538926205024910326572967”+
“23701913275725675285653248258265463092207058596522”+
“29798860272258331913126375147341994889534765745501”+
“18495701454879288984856827726077713721403798879715”+
“38298203783031473527721580348144513491373226651381”+
“34829543829199918180278916522431027392251122869539”+
“40957953066405232632538044100059654939159879593635”+
“29746152185502371307642255121183693803580388584903”+
“41698116222072977186158236678424689157993532961922”+
“62467957194401269043877107275048102390895523597457”+
“23189706772547915061505504953922979530901129967519”+
“86188088225875314529584099251203829009407770775672”+
“11306739708304724483816533873502340845647058077308”+
“82959174767140363198008187129011875491310547126581”+
“97623331044818386269515456334926366572897563400500”+
“42846280183517070527831839425882145521227251250327”+
“55121603546981200581762165212827652751691296897789”+
“32238195734329339946437501907836945765883352399886”+
“75506164965184775180738168837861091527357929701337”+
“62177842752192623401942399639168044983993173312731”+
“32924185707147349566916674687634660915035914677504”+
“99518671430235219628894890102423325116913619626622”+
“73267460800591547471830798392868535206946944540724”+
“76841822524674417161514036427982273348055556214818”+
“97142617910342598647204516893989422179826088076852”+
“87783646182799346313767754307809363333018982642090”+
“10848802521674670883215120185883543223812876952786”+
“71329612474782464538636993009049310363619763878039”+
“62184073572399794223406235393808339651327408011116”+
“66627891981488087797941876876144230030984490851411”+
“60661826293682836764744779239180335110989069790714”+
“85786944089552990653640447425576083659976645795096”+
“66024396409905389607120198219976047599490197230297”+
“64913982680032973156037120041377903785566085089252”+
“16730939319872750275468906903707539413042652315011”+
“94809377245048795150954100921645863754710598436791”+
“78639167021187492431995700641917969777599028300699”+
“15368713711936614952811305876380278410754449733078”+
“40789923115535562561142322423255033685442488917353”+
“44889911501440648020369068063960672322193204149535”+
“41503128880339536053299340368006977710650566631954”+
“81234880673210146739058568557934581403627822703280”+
“82616570773948327592232845941706525094512325230608”+
“22918802058777319719839450180888072429661980811197”+
“77158542502016545090413245809786882778948721859617”+
“72107838435069186155435662884062257473692284509516”+
“20849603980134001723930671666823555245252804609722”+
“53503534226472524250874054075591789781264330331690”;

String[] s2=s.split (“(?<=\\G…………………………………………..)");

for(int i=0;i<100;i++){

}
System.out.println("Sum "+sum);
System.out.println("to String "+sum.toString().substring(0, 10));

}

}

Miles

I dropped by to mention that you could also just use a float. They’re pretty much designed for the scenario of needing some precision, but not unlimited. Working solution with a float (sorry it’s in python not C#, but you get the picture):

sum = 0.0
for line in numberFile:
sum += float(line.strip())

return sum

Carl

I started from the other end. Add up the most significant digit of all 100 numbers and turn that into a string. That’s the start of your first 3 digits. Then move to the next most significant digit and sum all 100 of them. Merge that 3 digit total into the full total, one position to the right, accounting for carries into more significant digits of the total. Repeat this operation, moving one digit to the right each time. Once you get to a position where carries from less significant digit sums can’t affect the first 10 digits, you’re done. No need for bigint packages. Not as straightforward as adding up all the numbers, but a little more satisfying to program.

goatcoder

#include<iostream.h>
#include<conio.h>
#include<fstream.h>

int main(){
ifstream file;
file.open("data1.txt");
char ch, str[5000];
int i=0, k=0, j=0, arr[100][50];
unsigned long int sum[50];
while(!file.eof()){
ch=file.get();
str[i++]=ch;
}
for(i=0; i<100; i++){
for(j=0;j<50;j++){
arr[i][j]=str[k++]-48;
}
}

//input ends
for(j=49; j>=0; j–){
sum[j]=0;
for(i=0; i<100; i++){
sum[j]+=arr[i][j];
}
cout<<sum[j]<<endl;
}
cout<<endl;

for(i=49; i>0; i–){
sum[i-1]+=((sum[i]-(sum[i]%10))/10);
sum[i]%=10;
}
for(i=0;i<50;i++){
cout<<sum[i];
}

file.close();
return 0;
}

Gude

I solve it in few lines in Javascript:

var str =
`// paste numbers here
`;

“`
let list = str.split(String.fromCharCode(10)).map(s => Number(s.substring(0,12)));
let topD = list.reduce((a,b) => a + b).toString().substring(0,10); //str
console.log(topD);
“`