Sum of the digits of the number 2^1000

Question

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 power of 1000 (2^1000)?

Can anyone provide the solution or algorithm for this problem in java?

Answer 1

What’s wrong with simply counting it?

long sum = 0;
for (char c : java.math.BigInteger.valueOf(2).pow(1000).toString().toCharArray()) {
    sum += c - 48;
}

I should stop doing other people’s homework.

Answer 2

I won't provide code, but java.math.BigInteger should make this trivial.

Answer 3

2^1000 is a very large value, you would have to use BigIntegers. The algorithm would be something like:

import java.math.BigInteger;
BigInteger two = new BigInteger("2");
BigInteger value = two.pow(1000);
int sum = 0;
while (value > 0) {
  sum += value.remainder(new BigInteger("10"));
  value = value.divide(new BigInteger("10"));
}

Answer 4

something like that sould do it bute force: - although there is a nice analytic solution (think pen& paper) using mathematics - that may also work for numbers greater than 1000.

    final String bignumber = BigInteger.valueOf(2).pow(1000).toString(10);
 long result = 0;
 for (int i = 0; i < bignumber.length(); i++) {
  result += Integer.valueOf(String.valueOf(bignumber.charAt(i)));
 }
 System.out.println("result: " + result);

Answer 5

How can 2^1000 be alternatively expressed?

I don't remember much from my maths days, but perhaps something like (2^(2^500))? And how can that be expressed?

Find an easy way to calculate 2^1000, put the result in a BigInteger, and the rest is perhaps trivial.

Answer 6

Here is my solution:

public static void main(String[] args) {

 ArrayList<Integer> n = myPow(2, 100);

 int result = 0;
 for (Integer i : n) {
  result += i;
 }

 System.out.println(result);
}

public static ArrayList<Integer> myPow(int n, int p) {
 ArrayList<Integer> nl = new ArrayList<Integer>();
 for (char c : Integer.toString(n).toCharArray()) {
  nl.add(c - 48);
 }

 for (int i = 1; i < p; i++) {
  nl = mySum(nl, nl);
 }

 return nl;
}

public static ArrayList<Integer> mySum(ArrayList<Integer> n1, ArrayList<Integer> n2) {
 ArrayList<Integer> result = new ArrayList<Integer>();

 int carry = 0;

 int max = Math.max(n1.size(), n2.size());
 if (n1.size() != max)
  n1 = normalizeList(n1, max);
 if (n2.size() != max)
  n2 = normalizeList(n2, max);

 for (int i = max - 1; i >= 0; i--) {
  int n = n1.get(i) + n2.get(i) + carry;
  carry = 0;
  if (n > 9) {
   String s = Integer.toString(n);
   carry = s.charAt(0) - 48;
   result.add(0, s.charAt(s.length() - 1) - 48);
  } else
   result.add(0, n);
 }

 if (carry != 0)
  result.add(0, carry);

 return result;
}

public static ArrayList<Integer> normalizeList(ArrayList<Integer> l, int max) {
 int newSize = max - l.size();
 for (int i = 0; i < newSize; i++) {
  l.add(0, 0);
 }
 return l;
}

This code can be improved in many ways ... it was just to prove you can perfectly do it without BigInts.

The catch is to transform each number to a list. That way you can do basic sums like:

123456
+   45
______
123501

Answer 7

Sorry, can't resist the ambiguous question.

Clearly, 2^1000 will have every digit in it for most radices, so the answer for base-10 must be 45.

Other fun radices to consider:

In base-2, the answer is 1. In base-2^1000, the answer is 2^1000.

Answer 8

Alternatively, you could grab a double and manipulate its bits. With numbers that are the power of 2, you won't have truncation errors. Then you can convert it to string.

Having that said, it's still a brute-force approach. There must be a nice, mathematical way to make it without actually generating a number.

Answer 9

Apart from the Java aspect, this is a duplicate of this question

Answer 10

This problem is not simply asking you how to find the nearest big integer library, so I'd avoid that solution. This page has a good overview of this particular problem.

Answer 11

Bombe's solution is the best solution.It is very simple also

Answer 12

1.0715086071862673e+301 it is the answer of 2^1000

Answer 13

In[1162] := Plus @@ IntegerDigits[2^1000]
Out[1162] = 1366