Project Euler/16

Project Euler problem 16: https://projecteuler.net/problem=16

Problem 16 asks to find the sum of the digits of $ 2^{1000} $.

Brute Force Method

This is obviously much larger than the capacity of Java's int, $ 2^{32} $, or long, $ 2^{64} $. However, Java's math library has a big integer type built in that allows for arbitrary precision algebra. Solving this problem is as easy as learning how to call it. The number is not as large as it looks - it won't overwhelm a computer to actually compute it. Java computes it in less than a second.

$ time javac BigNum.java && java BigNum

real	0m0.630s
user	0m1.166s
sys	0m0.090s

The entire code consists of 2 steps and 8 lines.

The first step is to compute 2^1000,

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

and the second step is to sum up the digits of this number,

		char[] p = n.toString().toCharArray();
		int sum = 0;
		for(int j = 0; j < p.length; j++ ) { 
			int z = Character.digit(p[j],10);
			sum += z;
		}

Shortcuts?

This got me curious - if we had a painfully huge number, one that would take hours for a computer to properly compute all the digits of, how might we solve this problem without actually expanding out all the digits?

Here's a table I made of the sum of the digits of the powers of 2: