# Math problem Sum of a hundred 50 digit numbers.

• 12-18-2010, 06:11 PM
AcousticBruce
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

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

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

}

}
}[/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.
• 12-18-2010, 06:49 PM
Iron Lion
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.
• 12-18-2010, 06:55 PM
AcousticBruce
I'm not familiar with BigInteger. I will check that out.
• 12-18-2010, 07:05 PM
JosAH
This may be a stupid question but for a number, say, 12345, what are the first two digits? 12 or 45?

kind regards,

Jos
• 12-18-2010, 08:06 PM
AcousticBruce
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
Quote:

... 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.
Code:

• 12-19-2010, 09:33 AM
JosAH
Quote:

Originally Posted by AcousticBruce
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:

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
System.out.println(sum);

You decide if you need the leftmost digits or the rightmost digits.

kind regards,

Jos
• 12-19-2010, 11:44 AM
AcousticBruce
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 ""
• 12-19-2010, 11:56 AM
Iron Lion
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.
• 12-19-2010, 12:37 PM
AcousticBruce
I actually skipped a few. Perhaps I can do this one next. I will try to beat 57 seconds :)
• 12-19-2010, 12:50 PM
JosAH
Quote:

Originally Posted by Iron Lion
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:

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
• 12-19-2010, 01:28 PM
Iron Lion
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-19-2010, 01:39 PM
JosAH
Quote:

Originally Posted by Iron Lion
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
• 12-19-2010, 02:05 PM
Iron Lion
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):
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.
• 12-19-2010, 02:36 PM
JosAH
Quote:

Originally Posted by Iron Lion
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):
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