Problem of the Month (October 2003)

This month we are interested in power towers, stacks of powers of 2 in columns so that every column has the same digit sum. For example, here is a power tower with 4 columns, each with sum 10:

4096
 512
64  
   2
 1

What is the fewest number of powers of 2 that we can arrange in n columns, each of which has sum s? What is the fewest number needed if 2k is one of the powers included? What if we use powers of 3, or powers of some other base?

ANSWERS

Joseph DeVincentis and Philippe Fondanaiche considered the problem of finding which sums are possible using distinct powers and n columns. Here is what they found.

Possible Column Sums with n Columns
nColumn Sums
11, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
23, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18
34, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 23
45, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24
58, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 32
68, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 28, 32, 44

Jeremy Galvagni and Bill Clagett considered the values of M(n,s), the the fewest number of powers of 2 that can be arranged in n columns with sum s. Here is Bill's data:

Values of M(n,s)
n \ s 1 2 3 4 5 6 7 8 91011121314151617181920
111212231223233423343
222224242444354546555
333434343555465558787
444445354656576
5556565456665
666667556
77787856
8888886
999109
10101010
111111
121212
1313

Jeremy Galvagni conjectured that M(n,s) ≥ n, and that M(n,s) is increasing in n. Bill Clagett disproved both by finding this power tower:

65536
1024 
 2   
    1

Jeremy Galvagni also conjectured that M(n,8s)=ns, but then he found a counterexample M(3,16)=5. But he did manage to prove that M(an,s) ≤ a M(n,s) by noting that we can repeat the pattern, and possibly do better.

Here are the smallest towers known that include given powers of 2:

1   2   4   8   16   32   64   128   256   512   1024   2048
                4     1    2   16    4     256   32     64  
                1              4      1     2     2      4  
                               2           1       2      4 


4096   8192   16384   32768   65536   131072   262144   524288
 512    512   32      16      1024    2048        512   16    
64      512       4   4        2      512        4         4  
   2     16     4        2        1       16   4          4   
 1     4      4         1              4           1       2  
        1       1                       1               2

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 10/26/03.