Results 1 to 14 of 14
 12182010, 05:11 PM #1Senior Member
 Join Date
 Dec 2010
 Location
 Indiana
 Posts
 202
 Rep Power
 4
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 onehundred 50digit 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[place1] += Integer.parseInt(stringParts[i].substring(place1,place)); } } int pool = 0; String poolString; String longAnswer = ""; for (int i = 50; i > 1; i) { intLines[i1] += pool; poolString = Integer.toString(intLines[i1]); 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]
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; 12182010 at 09:28 PM.
 12182010, 05:49 PM #2Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 4
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; 12182010 at 05:59 PM.
 12182010, 05:55 PM #3Senior Member
 Join Date
 Dec 2010
 Location
 Indiana
 Posts
 202
 Rep Power
 4
I'm not familiar with BigInteger. I will check that out.
 12182010, 06:05 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,337
 Blog Entries
 7
 Rep Power
 20
This may be a stupid question but for a number, say, 12345, what are the first two digits? 12 or 45?
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 12182010, 07:06 PM #5Senior Member
 Join Date
 Dec 2010
 Location
 Indiana
 Posts
 202
 Rep Power
 4
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; 12182010 at 09:06 PM.
 12192010, 08:33 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,337
 Blog Entries
 7
 Rep Power
 20
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);
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 12192010, 10:44 AM #7Senior Member
 Join Date
 Dec 2010
 Location
 Indiana
 Posts
 202
 Rep Power
 4
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 ""
 12192010, 10:56 AM #8Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 4
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.
 12192010, 11:37 AM #9Senior Member
 Join Date
 Dec 2010
 Location
 Indiana
 Posts
 202
 Rep Power
 4
I actually skipped a few. Perhaps I can do this one next. I will try to beat 57 seconds :)
 12192010, 11:50 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,337
 Blog Entries
 7
 Rep Power
 20
Yup, I just solved it: the nth 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
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 12192010, 12:28 PM #11Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 4
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 :)
 12192010, 12:39 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,337
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 12192010, 01:05 PM #13Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 4
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
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.
 12192010, 01:36 PM #14
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,337
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

Math: pentagonal numbers
By Latanyar in forum New To JavaReplies: 7Last Post: 10102010, 03:14 PM 
Roundind up numbers using Math.ceil
By Allspark in forum New To JavaReplies: 1Last Post: 09082010, 05:15 AM 
Express 240 as'Two hundred and forty'
By j3sr in forum New To JavaReplies: 2Last Post: 01282010, 11:11 AM 
Math Related Problem
By perito in forum Advanced JavaReplies: 1Last Post: 03212008, 08:53 AM 
Math Related Problem
By perito in forum New To JavaReplies: 3Last Post: 03202008, 05:22 PM
Bookmarks