Project Euler 13: Sum of 50-digit numbers

Written by on 7 December 2010

Topics: Project Euler

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;
StreamReader r = new StreamReader(filename);

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

As usual the source code is available for download.

22 Comments For This Post I'd Love to Hear Yours!

  1. Sasa says:

    This is a very elegant solution.

    Respect.

  2. Kristian says:

    I think the short answer to that is thank you 🙂

  3. Guy David says:

    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);
    
  4. Kristian says:

    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

  5. saveen says:

    //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]);
    }

    Console.Read();
    }
    }
    }

  6. vincian says:

    #!/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..

  7. vincian says:

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

  8. Sidhant says:

    //Beautiful

    #include
    using namespace std;
    int main(){
    int no[100][50];
    int finale[53];
    int temp,counter=0,carry=0,tadd=0,normal;
    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++){
    tadd+=no[j][i];
    //cout<<no[j][i]<<"\n";
    //cout<<"Carry="<<carry<<"\n";
    //cout<<normal;
    }
    tadd+=carry;
    normal=tadd%10;
    carry=(tadd-normal)/10;
    cout<<"TADD="<<tadd<<"\n";
    tadd=0;
    cout<<"Normal="<<normal<<"\n";
    cout<<"CARRY="<<carry<<"\n";
    }
    //cout<<no[0][50];
    cin.get();
    }

  9. Sidhant says:

    #include
    using namespace std;
    int main(){
    int no[100][50];
    int finale[53];
    int temp,counter=0,carry=0,tadd=0,normal;
    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++){
    tadd+=no[j][i];
    //cout<<no[j][i]<<"\n";
    //cout<<"Carry="<<carry<<"\n";
    //cout<<normal;
    }
    tadd+=carry;
    normal=tadd%10;
    carry=(tadd-normal)/10;
    cout<<"TADD="<<tadd<<"\n";
    tadd=0;
    cout<<"Normal="<<normal<<"\n";
    cout<<"CARRY="<<carry<<"\n";
    }
    //cout<<no[0][50];
    cin.get();
    }

  10. Gabe says:

    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.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.math.BigInteger;

    public class LargeSum {
    public static void main(String[] args) throws FileNotFoundException {
    BufferedReader br = new BufferedReader(new FileReader(“C:\\Users\\P67263\\workspace\\Practice\\src\\ProjectEuler\\problem13.txt”));;
    try {
    String line = br.readLine();
    BigInteger largeNum;
    BigInteger sum = BigInteger.valueOf(0);
    long largeNumLong = 0L;
    long sumLong = 0L;

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

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

    System.out.println();
    line = br.readLine();
    }

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

    }

    }

  11. Kristian says:

    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.

  12. Michael says:

    @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.

  13. Kristian says:

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

  14. Diego says:

    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’),
    readline = require(‘readline’);

    var rd = readline.createInterface({
    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 ) {
    sum = sum.add(bigArray[i]);
    }
    return sum.toString().substr(0,10); // Wrong Answer! 5504722300, took 8ms
    //return bigArray.length;
    };

    return this;
    }());

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

  15. Noah says:

    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];
    
    private static void Menu()
    {
      DateTime startTime = DateTime.Now;
    
      string path = @"TextFiles\Problem_13.txt";
    
      using (StreamReader sr = new StreamReader(path))
      {
        for (int i = 0; i < Size; i++)
          number[i] = sr.ReadLine();
      }
    
      String sum = AddLrgInt(number[0], number[1]);
    
      for (int i = 2; i < Size; i++)
        sum = AddLrgInt(sum, number[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();
    
        // Add leading "0"s if we lost them in ulong summation.
        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;
    }
    
  16. Noah says:

    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){}
  17. Govind says:

    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();
    }
    }
    }

  18. Jean-Marie Hachey says:

    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
    (Reference added: System.Numerics)
    3) Java calculator
    http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
    4) Microsoft Office Excel (2007)

  19. kazititu says:

    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++){
    sum=sum.add(new BigInteger(s2[i]));

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

    }

    }

  20. Miles says:

    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):

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

    return sum

    print(addBigNumbers(open(‘problem13.txt’, ‘r’)))

  21. Carl says:

    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.

  22. goatcoder says:

    #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;
    }

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.