• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

project Euler problem 16

 
Randall Twede
Ranch Hand
Posts: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 3751
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
my understanding is that BigInteger can be however big it has to be. no limit
 
Randall Twede
Ranch Hand
Posts: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2675
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
oh...awesome!
thank you so much
 
Campbell Ritchie
Sheriff
Posts: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And the reason you were getting that Exception is that you can’t parse that double to an int.
 
Randall Twede
Ranch Hand
Posts: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about without solving it without using BigInteger? Just for fun.
 
Matthew Brown
Bartender
Posts: 4565
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4363
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Look in the Java™ Language specification; you find a char is an unsigned integer.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic