# project Euler problem 16

Randall Twede
Ranch Hand
Posts: 4489
3
i am trying to solve this

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

here is my code so far

this seems to work for the example(2^15) but not for the actual problem(2^1000)
my first system.out.println is equal to what i get from the windows calculator program
1.0715086071862673E301
then i cast it to a long and get this
9223372036854775807
which looks reasonable but gives the wrong answer. i am thinking the number is even too big for a long.
i am not sure this is even the best way to approach this problem. changing from a double to a long to a string and then back to a long then back to a string.
any help or observation appreciated.

Martin Vajsar
Sheriff
Posts: 3752
62
Yes, that number is way too high. Long can take numbers up to 2^63. 2^1000 is much larger.

Though you might try to take on this using BigInteger, I'd say the correct approach involves mathematical tricks, not programming ones.

Randall Twede
Ranch Hand
Posts: 4489
3
thanks for the answer. that is what i thought. i will try BigInteger since i also need to learn that class better for something else. i still suspect there is a better way than changing it to a string but it was all i could think of.

Saurabh Pillai
Ranch Hand
Posts: 524
I am not able to solve this myself either yet.

My question is, how many bits long BigInteger is? Because whatever the datatype we choose, should be able to CONTAIN the final result. String can contain it but you can not do math operation on it.

Also somehow I feel shift operators might be of some help here. Not sure if this information is useful but also keep in mind that, 2^15 = 2^10 * 2^5. (Distribution of power)

Randall Twede
Ranch Hand
Posts: 4489
3
well it is even more convoluted now but i think i am close to an answer.

i get a runtime exception though
java.lang.NumberFormatException
at line 8

Randall Twede
Ranch Hand
Posts: 4489
3
my understanding is that BigInteger can be however big it has to be. no limit

Randall Twede
Ranch Hand
Posts: 4489
3
i think maybe i will have to create a BigDecimal first and change that to a BigInteger to fix the runtime error?

Tim Moores
Bartender
Posts: 3004
47
The point is, 2^1000 is too big for a double. You can't construct the BigInteger that way. But there's no need - BigInteger has a pow method.

Randall Twede
Ranch Hand
Posts: 4489
3
oh...awesome!
thank you so much

Campbell Ritchie
Sheriff
Posts: 50644
83
And the reason you were getting that Exception is that you can’t parse that double to an int.

Randall Twede
Ranch Hand
Posts: 4489
3
i solved it! thank you all.
i still think there might be a better way than changing it to a String to parse it but it works, and quickly

Saurabh Pillai
Ranch Hand
Posts: 524
How about without solving it without using BigInteger? Just for fun.

Matthew Brown
Bartender
Posts: 4568
9
One thing to slightly simplify it: you need BigInteger to contain 2^1000, but you don't need it to contain the sum of the digits. And you can convert a digit character to the value of the digit by simply subtracting '0'.

Randall Twede
Ranch Hand
Posts: 4489
3
Mathew, exactly, but i didn't want to post the solution.

i dont see how i can solve it without BigInteger. however, many people have solved it in many other languages. now that i have solved it i can see their solutions

Randall Twede
Ranch Hand
Posts: 4489
3
And you can convert a digit character to the value of the digit by simply subtracting '0'.

i didn't know that, but the rest of what you said i did

Campbell Ritchie
Sheriff
Posts: 50644
83
Look in the Java™ Language specification; you find a char is an unsigned integer.