Results 1 to 14 of 14
  1. #1
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default Math problem Sum of a hundred 50 digit numbers.

    I am trying to figure out this math problem.

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

    Basically I copied the 50 digit numbers from the link about and pasted them into the IDE. I named it hugeString.


    1) Do you think I was on the right track with idea 1 or 2 or should I think of this differently?

    2) Could both of these work if coded right?

    3) Are there any bad coding habits that you can see that I should change? I really want to start out right, please let me know.


    I hope my code isn't too inefficient to read.

    This is my idea 1

    Java Code:
    public class Sum50Digits {
        public static void main(String[] args) {
    
            String hugeNum = "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";
    
            [COLOR="Red"]int[] intLines = new int[50];
            String[] stringLines = new String[50];
            for (int i = 0; i > 50; i--) {
                stringLines[i] = Integer.toString(intLines[i]);
            }
    
            double dblTotal = 0;
            String dblString;
    
            for (int place = 50; place > 0; place--) {
                for (int i = 0; i < 100; i++) {
                    dblTotal += Double.parseDouble(hugeNum.substring(i*50, (i*50)+50));
    
                }
            }
            dblString = Double.toString(dblTotal);
            System.out.println(dblString.replace(".","").substring(0,10));[/COLOR]


    This was my second idea
    Java Code:
    [COLOR="Red"]
            String[] stringParts = new String[100];
            int[] intLines = new int[50];
            String[] stringLines = new String[50];
    
            for (int place = 50; place > 0; place--) {
                for (int i = 0; i < 100; i++) {
                    stringParts[i] = hugeNum.substring(i*50, (i*50)+50);
                    intLines[place-1] += Integer.parseInt(stringParts[i].substring(place-1,place));
                }
    
            }
            int pool = 0;
            String poolString;
            String longAnswer = "";
    
            for (int i = 50; i > 1; i--) {
                intLines[i-1] += pool;
                poolString = Integer.toString(intLines[i-1]);
                pool += Integer.parseInt(poolString.substring(0,poolString.length()-1));
                longAnswer += Integer.parseInt(poolString.substring(poolString.length()-1));
    
    
    
            }
            String answer = new StringBuffer(longAnswer).reverse().toString();
            System.out.println(answer.substring(0,10));
    
            
        }
    }[/COLOR]
    hugeString: Basically all the 100x50 digits.
    stringParts[]: broke up hugeString into 100 separate 50 digit numbers stored to this array.
    intLines[]: is the sum of the same digit of all the 50 digit numbers stored to this array.
    Last edited by AcousticBruce; 12-18-2010 at 09:28 PM.

  2. #2
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    My solution involved copying the source numbers to a text file, using a Scanner to read each line in as a BigInteger, and then copy the final BigInteger to a string.
    Last edited by Iron Lion; 12-18-2010 at 05:59 PM.

  3. #3
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    I'm not familiar with BigInteger. I will check that out.

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    This may be a stupid question but for a number, say, 12345, what are the first two digits? 12 or 45?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    for the manual addition (the 2nd idea)

    My program starts from the right and moves left.
    the final set of numbers answer ended up being in reverse.
    So I just reversed it and substring() the first 10 digits.

    my idea was to do something like this

    ... 5th
    332 4th
    -423 3rd
    --522 2nd
    ---422 1st
    ------------
    the 1st string I would take the last digit "2" and it now becomes the end of my answer string.
    then the left over would be added to the 2nd string as an int. I would take the digit on the right and add it to my answer string "42"
    then it would add the remainder to the 3rd.
    i would take the digit on right and add it "642"
    then take the remainder and add it to the 4th.
    take digit on right and add "5642" ... and so on.
    So this will put it together from right to left. I will then take the 10 digit sub string from the beginning and that should have been the answer.

    Really this all confused me too. I ended up reversing my answer string at the end because im sure it was backwards.
    Java Code:
    String answer = new StringBuffer(longAnswer).reverse().toString();
            System.out.println(answer.substring(0,10));

    Last edited by AcousticBruce; 12-18-2010 at 09:06 PM.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by AcousticBruce View Post
    for the manual addition (the 2nd idea)

    My program starts from the right and moves left.
    the final set of numbers answer ended up being in reverse.
    So I just reversed it and substring() the first 10 digits.
    Why all that juggling? Instead of starting with one huge String having those 100 numbers glued together, use a String array with 100 Strings in it, fifty digits each and use the BigInteger class to do the hard work:

    Java Code:
    String[] nums= { ... }; // hundred 50 digit numbers in String form
    BigInteger sum= BigInteger.ZERO;
    for (int i= 0; i < nums.length; i++) // add all numbers
       sum= sum.add(new BigInteger(nums[i]));
    System.out.println(sum);
    You decide if you need the leftmost digits or the rightmost digits.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    This Is what i love about progammong u can be a total newb and find a different way to do things. I ended up using Double.parseint and adding them together and removing thw "." for ""

  8. #8
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    Out of interest, did you do problem 12? My solution gets the answer in the end, but takes 57.5 seconds and uses 58 lines of code in addition to the PrimeNumbers class I'd written for a previous question, so I'm thinking there must be a much more efficient way of doing it.

  9. #9
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    I actually skipped a few. Perhaps I can do this one next. I will try to beat 57 seconds :)

  10. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Iron Lion View Post
    Out of interest, did you do problem 12? My solution gets the answer in the end, but takes 57.5 seconds and uses 58 lines of code in addition to the PrimeNumbers class I'd written for a previous question, so I'm thinking there must be a much more efficient way of doing it.
    Yup, I just solved it: the n-th triangle number is n*(n+1)/2 and I looped over the first 100000 triangle numbers using my own little language RPL and it solved it in one second or so; here's the code:

    Java Code:
    'triangle
    'lambda n = {
    	n divisors
    	'n swap = clr
    	n
    }
    =
    
    'lambda n = {
    	locals m nil end
    	'm n n ++ * 2 / = m triangle
    	if 500 > then { m swriteln n swriteln 0 stop}
    }
    100000 iter
    It found the 12375th triangle number (being 76576500) which has 575 divisors (excluding the number itself); is it the correct answer?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    Yep, that's right. The number of divisors is supposed to include the number itself, not that it makes a difference on this occasion.

    Looks like I've got some work to do bringing mine up to speed :)

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Iron Lion View Post
    Yep, that's right. The number of divisors is supposed to include the number itself, not that it makes a difference on this occasion.

    Looks like I've got some work to do bringing mine up to speed :)
    Finding the divisors of a number is the most time consuming operation but you can speed it up a bit: suppose you have found all divisors of a number n up to sqrt(n); the other divisors can easily be found then, e.g. if n == 100 the divisors are 1, 2, 4, 5 and 10 because 10 == sqrt(100). The other divisors are 100/1, 100/2, 100/4 and 100/5. That saves you the search for the numbers 11, 12 ... 99. It gets more important for larger values of n.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    My solution revolved around combinations of prime factors. For example, if you arrange the powers of the prime factors as follows (in this case, n=60):
    Java Code:
    2^0    3^0    5^0
    2^1    3^1    5^1
    2^2
    then, let r = 1, and then iterate through each column of the table and multiply r by the number of powers of that prime.

    Update: After running it again, it seems that out of the program's 57.5 second runtime, 57 seconds is spent finding 2000000 primes. This is much more than is necessary; cutting it down to 100000 brings the runtime down to 1.319s.

  14. #14
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,654
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Iron Lion View Post
    My solution revolved around combinations of prime factors. For example, if you arrange the powers of the prime factors as follows (in this case, n=60):
    Java Code:
    2^0    3^0    5^0
    2^1    3^1    5^1
    2^2
    then, let r = 1, and then iterate through each column of the table and multiply r by the number of powers of that prime.

    Update: After running it again, it seems that out of the program's 57.5 second runtime, 57 seconds is spent finding 2000000 primes. This is much more than is necessary; cutting it down to 100000 brings the runtime down to 1.319s.
    I understand what you're doing but are you doing that for every number over and over again? My guess is that there is more clever trickery possible; for a triangle number we already know that it has the form n*(n+1)/2 so if we have the prime factors for the number n we can deduce the other prime factors. For the n+1thn triangle number we only have to find the prime factors for n+2 (we already had them for number n+1 and number n) ... I have to think about it ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Math: pentagonal numbers
    By Latanyar in forum New To Java
    Replies: 7
    Last Post: 10-10-2010, 03:14 PM
  2. Roundind up numbers using Math.ceil
    By Allspark in forum New To Java
    Replies: 1
    Last Post: 09-08-2010, 05:15 AM
  3. Express 240 as'Two hundred and forty'
    By j3sr in forum New To Java
    Replies: 2
    Last Post: 01-28-2010, 11:11 AM
  4. Math Related Problem
    By perito in forum Advanced Java
    Replies: 1
    Last Post: 03-21-2008, 08:53 AM
  5. Math Related Problem
    By perito in forum New To Java
    Replies: 3
    Last Post: 03-20-2008, 05:22 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •