Java: summing all digits 2 ^ 1000

Question

I am trying to solve the problem of Project Euler No. 16, where I need to sum all the numbers 2 ^ 1000. I came across so many. My program worked for any number below 10 ^ 16, but then failed. This told me that my logic is correct. I went ahead and converted all the variables and methods to BigDecimal, but now the program does not work correctly. It compiles as it is, and there is no error; it just doesn't end. Does anyone have an idea on where I made a mistake here?

import java.math.BigDecimal; import java.math.RoundingMode; public class Powerdigitsum { private static final BigDecimal one = new BigDecimal("1"); private static final BigDecimal ten = new BigDecimal("10"); private static BigDecimal sumofDigits(BigDecimal n){ BigDecimal sum = new BigDecimal("0"); while(n.compareTo(one) == 1 || n.compareTo(one) == 0){ sum.add(n.remainder(ten)); n.divide(ten); n = n.setScale(0, RoundingMode.FLOOR); } return sum; } public static void main(String[] args) { final double the_number = Math.pow(2,1000); final double test = 15; final BigDecimal two_to_the_thousandth_power = new BigDecimal(test); System.out.println(sumofDigits(two_to_the_thousandth_power)); } } 

Answer 1

The whole method is wrong. See this:

 private static BigInteger sumOfDigits(BigInteger n) { BigInteger sum = BigInteger.ZERO; while (n.compareTo(BigInteger.ZERO) == 1) { sum = sum.add(n.remainder(ten)); n = n.divide(ten); } return sum; } 

You had to compare with zero, not with one. And you need to assign values ​​to BigIntegers and BigDecimals, their methods do nothing on their own, instances of these classes are immutable.

For integers, it is usually better to use BigInteger . The decimal part (which gets there from the division) is simply discarded.

Answer 2

Just use BigInteger correctly:

BigInteger a = new BigInteger("2").pow(1000);

Answer 3

 final double the_number = Math.pow(2,1000); 

This will not work because the_number not large enough to accept the result. You need to convert the pow call to BigInteger :

 BigInteger result = new BigInteger("2").pow(1000); 

But be careful .. this may take some time.

Answer 4

Do not use the constructor BigDecimal(double) : it is limited to the primitive type double , which cannot represent 2 ^ 1000.

You can use BigInteger . Something in this direction should work (maybe suboptimal, but ...):

 public static void main(final String... args) { // 2^1000 final BigInteger oneTo2000 = BigInteger.ONE.shiftLeft(1000); BigInteger digitSum = BigInteger.ZERO; // We don't want to split against the empty string, the first element would be "" for (final String digit: oneTo2000.toString().split("(?<=.)")) digitSum = digitSum.add(new BigInteger(digit)); System.out.println(digitSum); } 

Answer 5

 import java.math.BigInteger; public class Problem16 { public static void main(String[] args) { BigInteger number2 = new BigInteger("2"); BigInteger number3 = new BigInteger("0"); number3 =number2.pow(1000); String str = number3.toString(); BigInteger sum = new BigInteger("0"); for(int i=0; i<str.length(); i++) { char c= str.charAt(i); int value = Character.getNumericValue(c); BigInteger value2 = new BigInteger(Integer.toString(value)); sum =sum.add(value2) ; } System.out.println(sum); } } 

Answer 6

IF YOU THINK, THE BIGINTEGER IS AND / OR DOES NOT HAVE IT / STILL TAKES HOW TO USE IT, THIS ALGORITHM IS THE WAY.

Think about how you would calculate 2 ^ 1000 manually. You start with 2 ^ 1 and multiply by two. Now note that the number of digits of two degrees increases by 1 for AT LEAST every 3 degrees (maybe after 4 degrees, for example, from 1024 to 8192). So make a jagged 2D array like this

 int a[][]= new int[1000][]; for(int i=0;i<1000;i++) { a[i]= new int[1+(i/3)]; } 

Then initialize [0] [0] to 2. After that, you want to write a for loop so that each line is filled from the rightmost spot. Therefore, make the two variables “digit” and “carry over”. The digit is the number that you will enter in the line that you are working on, and the hyphenation is the one you are going to use for the next calculation, and add to the product 2 and any digit that you multiply. Be careful with the order when you update the digit, transfer and reinitialize them to zero after each calculation. I think the hardest part comes up with the limitations of the for loop, so it matches each of the three things. You can make it simpler by simply making a triangular gear array that grows one row. I did it like that. Here is all my code.

 import java.util.*; public class ProjectEuler16 { public static void main(String[] args) { long t1=System.currentTimeMillis(); ProjectEuler16 obj = new ProjectEuler16(); System.out.println(obj.bigNumHandler()); long t2= System.currentTimeMillis(); System.out.println(t2-t1); } int bigNumHandler() { int a[][] = new int[1000][]; for(int i=0;i<1000;i++) { a[i]= new int[1+(i/3)]; } a[0][0]=2; for(int i=1;i<1000;i++) { int carry=0; int digit=0; int f=0; if(i%3==0) { f=1; } for(int j=a[i-1].length-1+f;j>=0;j--) { if(j==0&f==1) { a[i][0]=carry; } else { digit=((2*a[i-1][jf])+carry)%10; carry=((2*a[i-1][jf])+carry)/10; a[i][j]=digit; } } } int sum=0; for(int k=0;k<a[999].length;k++) { sum=sum+a[999][k]; } return sum; } } 

Please note that the last line lists the numbers for 2 ^ 1000. I think you can figure out how to sum the numbers. The answer to this question took about 5 seconds.

Answer 7

decision::

 import java.math.BigInteger; public class PR9 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BigInteger zero=BigInteger.valueOf(0); BigInteger ten=BigInteger.valueOf(10); BigInteger sum=zero; BigInteger a = new BigInteger("2").pow(1000); while(a.compareTo(zero)>0){ sum=sum.add(a.mod(ten)); a=a.divide(ten); } System.out.println(sum); } } 

output:::
1366

Answer 8

 import java.math.BigInteger; public class P16 { public static BigInteger digitSum(int n) { BigInteger sum = BigInteger.ZERO; BigInteger number = new BigInteger("2").pow(n); while (number.compareTo(BigInteger.ZERO) == 1) { BigInteger remainder = number.remainder(BigInteger.TEN); sum = sum.add(remainder); number = number.divide(BigInteger.TEN); } return sum; } public static void main(String[] args) { final double START = System.nanoTime(); System.out.println(digitSum(Integer.parseInt(args[0]))); final double DURATION = System.nanoTime() - START; System.out.println("Duration: " + DURATION / 1000000 + "ms."); } } 

Although it is possible to solve this problem without using BigIntegers, it is clear that they speed up the code. It took me about 4 ms to find the answer.