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 2^{k} is one of the powers included? What if we use powers of 3, or powers of some other base?

n | Column Sums |
---|---|

1 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 |

2 | 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18 |

3 | 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 23 |

4 | 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24 |

5 | 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 32 |

6 | 8, 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:

n \ s | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 2 | 3 | 3 | 4 | 2 | 3 | 3 | 4 | 3 |

2 | 2 | 2 | 2 | 2 | 4 | 2 | 4 | 2 | 4 | 4 | 4 | 3 | 5 | 4 | 5 | 4 | 6 | 5 | 5 | 5 |

3 | 3 | 3 | 4 | 3 | 4 | 3 | 4 | 3 | 5 | 5 | 5 | 4 | 6 | 5 | 5 | 5 | 8 | 7 | 8 | 7 |

4 | 4 | 4 | 4 | 4 | 5 | 3 | 5 | 4 | 6 | 5 | 6 | 5 | 7 | 6 | ||||||

5 | 5 | 5 | 6 | 5 | 6 | 5 | 4 | 5 | 6 | 6 | 6 | 5 | ||||||||

6 | 6 | 6 | 6 | 6 | 7 | 5 | 5 | 6 | ||||||||||||

7 | 7 | 7 | 8 | 7 | 8 | 5 | 6 | |||||||||||||

8 | 8 | 8 | 8 | 8 | 8 | 6 | ||||||||||||||

9 | 9 | 9 | 10 | 9 | ||||||||||||||||

10 | 10 | 10 | 10 | |||||||||||||||||

11 | 11 | 11 | ||||||||||||||||||

12 | 12 | 12 | ||||||||||||||||||

13 | 13 |

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.