From charlesreid1

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


SumOfDigitsOfPowersOf2.png

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://charlesreid1.com:3000/cs/euler/src/master/scratch/Round1_001-020/016

Flags