programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Jeanne Boyarsky
• Devaka Cooray
• Paul Clapham
Sheriffs:
• Tim Cooke
• Knute Snortum
• Bear Bibeault
Saloon Keepers:
• Ron McLeod
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Ganesh Patekar
Bartenders:
• Frits Walraven
• Carey Brown
• Tim Holloway

project Euler problem 16

Ranch Hand
Posts: 4702
9
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.

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: 4702
9
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.

Ranch Hand
Posts: 541
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: 4702
9
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: 4702
9
my understanding is that BigInteger can be however big it has to be. no limit

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

Saloon Keeper
Posts: 5559
143
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: 4702
9
oh...awesome!
thank you so much

Marshal
Posts: 64618
225
And the reason you were getting that Exception is that you can’t parse that double to an int.

Randall Twede
Ranch Hand
Posts: 4702
9
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: 541
How about without solving it without using BigInteger? Just for fun.

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: 4702
9
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: 4702
9

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
Marshal
Posts: 64618
225
Look in the Java™ Language specification; you find a char is an unsigned integer.

 You totally ruined the moon. You're gonna hafta pay for that you know. This tiny ad agrees: how do I do my own kindle-like thing - without amazon https://coderanch.com/t/711421/engineering/kindle-amazon