File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes project Euler problem 16 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "project Euler problem 16" Watch "project Euler problem 16" New topic
Author

project Euler problem 16

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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.

SCJP
Visit my download page
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Sep 12, 2008
Posts: 507
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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

i think maybe i will have to create a BigDecimal first and change that to a BigInteger to fix the runtime error?
Tim Moores
Rancher

Joined: Sep 21, 2011
Posts: 2408
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

Joined: Oct 21, 2000
Posts: 4340
    
    2

oh...awesome!
thank you so much
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
And the reason you were getting that Exception is that you can’t parse that double to an int.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Sep 12, 2008
Posts: 507
How about without solving it without using BigInteger? Just for fun.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4372
    
    8

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Oct 13, 2005
Posts: 38481
    
  23
Look in the Java™ Language specification; you find a char is an unsigned integer.
 
Consider Paul's rocket mass heater.
 
subject: project Euler problem 16