Project Euler/16

Problem Overview

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.

It's important to keep a sense of scale - the 2 in the base means $ 2^{1000} $ is way smaller than $ 10^{1000} $. In fact, the number is not as large as it looks, and it is no sweat for a computer to handle 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:

exp sum digits 100 115 110 121 120 172 130 196 140 202 150 235 160 205 170 238 180 244 190 259 200 256 210 280 220 349 230 355 240 361 250 286 260 328 270 361 280 376 290 409 300 424 310 430 320 400 330 406 340 475 350 490 360 532 370 439 380 508 390 523 400 547 410 526 420 550 430 574 440 625 450 559 460 646 470 706 480 658 490 682 500 679 510 667 520 745 530 742 540 730 550 727 560 760 570 811 580 826 590 769 600 829 610 790 620 841 630 784 640 871 650 886 660 919 670 880 680 877 690 892 700 961 710 922 720 955 730 1069 740 1030 750 1027 760 988 770 967 780 1063 790 1105 800 1048 810 1144 820 1177 830 1111 840 1090 850 1177 860 1138 870 1081 880 1195 890 1273 900 1198 910 1231 920 1309 930 1333 940 1312 950 1228 960 1414 970 1321 980 1399 990 1279 1000 1366 1010 1327 1020 1342 1030 1312 1040 1408 1050 1423 1060 1420 1070 1426 1080 1522 1090 1492 1100 1561 1110 1468 1120 1393 1130 1597 1140 1567 1150 1564 1160 1597 1170 1522 1180 1582 1190 1633 1200 1729 1210 1708 1220 1543 1230 1711 1240 1771 1250 1732 1260 1666 1270 1735 1280 1723 1290 1738 1300 1816 1310 1732 1320 1801 1330 1816 1340 1795 1350 1846 1360 1879 1370 1957 1380 1927 1390 1933 1400 1975 1410 1918 1420 1924 1430 1948 1440 1900 1450 2113 1460 1957 1470 1999 1480 2104 1490 1993 1500 2035 1510 2122 1520 1984 1530 2017 1540 2059 1550 2155 1560 2125 1570 2167 1580 2119 1590 2098 1600 2176 1610 2209 1620 2359 1630 2167 1640 2173 1650 2098 1660 2257 1670 2263 1680 2278 1690 2266 1700 2308 1710 2296 1720 2320 1730 2326 1740 2377 1750 2473 1760 2407 1770 2449 1780 2491 1790 2542 1800 2467 1810 2437 1820 2461 1830 2521 1840 2482 1850 2533 1860 2413 1870 2581 1880 2515 1890 2539 1900 2581 1910 2731 1920 2701 1930 2545 1940 2749 1950 2566 1960 2725 1970 2659 1980 2755 1990 2635 2000 2704

Does this offer any kind of shortcut? Not exactly - although there's an overall pattern, the local behavior seems unpredictable. Furthermore, there is no inverse problem, so we can't explore numbers in a local region (extrapolating from the curve above) and test if they are solutions.

Code

Here is the solution in code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round1_001-020/016