## Follow-up: Weird sums

What numbers can 1,2,4,8,16,… etc “form”? Well, every number can be “formed” by summing various powers of 2. For example, 13 = 1 + 4 + 8.

In this way, we could say that a power of 2, say 64, is “full of divisors” since it has enough divisors to form any number up to 64. Its divisors are of course 1, 2, 4, 8, 16 and 32, and we can form any number from 1 to 63 by summing up these divisors as needed.

But what other numbers of “full of divisors”?

22 is not “full of divisors” since 1, 2 and 11 are obviously not enough to form any number from 1 to 21.

But 88 is full of divisors! Not hard to see why if you take a close look…

So here is a quick puzzle that will help us out with the solution to Perfect Sums

Check that: given any number Q, there is a k so that 2k Q is full of divisors. (For 11, k=3 and 23 11 is full of divisors.)

Why is 88 “full of divisors”? 1, 2, 4, 8 can form any number up to 11, and 11, 22, 44 can form any multiple of 11 up to 77. So all together 1,2,4,8,11,22,44 can form any number from 1 to 87.

1. ### Shawn said,

April 10, 2012 at 12:35 pm

I guess for a number to be “full of divisors”, you would need to be able to sum to any number up to that number using each of its integer divisors only once. Otherwise, you could sum to any positive integer by adding 1 repeatedly.

2. ### strauss said,

April 18, 2012 at 8:51 am

! Yep !