On 09/08/2012 11:15 AM, Invisible wrote:
> So, what happens if we start with the only integers being 5 and 8. What
> other integers can we produce by adding these?

> According to my simulations, you can make /every/ number above 27. So 27
> is the highest number that you cannot make.

I find it rather surprising that /every/ number can be made this way. So 
I set out to discover why...

Suppose we start with all the numbers, and then cross off all the 
multiples of 5. We then end of with something like

   0000000000111111111122222222223333333333444444444455555555556666666666
   0123456789012345678901234567890123456789012345678901234567890123456789
   X    X    X    X    X    X    X    X    X    X    X    X    X    X

So these are all the numbers which we can make simply by adding 5s together.

Now suppose we add a single 8. Well, that shifts the whole thing 8 units 
to the right, obviously.

   0000000000111111111122222222223333333333444444444455555555556666666666
   0123456789012345678901234567890123456789012345678901234567890123456789
   X    X    X    X    X    X    X    X    X    X    X    X    X    X
           X    X    X    X    X    X    X    X    X    X    X    X    X

Everything marked in the top row can be made using only 5s. Everything 
on the row below can be made with 5s and a single 8. Continuing this 
process,

   0000000000111111111122222222223333333333444444444455555555556666666666
   0123456789012345678901234567890123456789012345678901234567890123456789
   X    X    X    X    X    X    X    X    X    X    X    X    X    X
           X    X    X    X    X    X    X    X    X    X    X    X    X
                   X    X    X    X    X    X    X    X    X    X    X
                           X    X    X    X    X    X    X    X    X    X
                                   X    X    X    X    X    X    X    X
   X    X  X X  X XX X XX XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

The bottom row is the union of all the rows above it.

As you can see, 8 mod 5 = 3, so by the time you get far enough to the 
right, every row is 3 units out of step with the one above. 3+3 = 6, and 
6 mod 5 = 1, so the second row is 3 units out of step with the one 
above, but only 1 unit out of step with the row above that. Put simply, 
if you make 5 rows, together they cover *all* the holes, and *every* 
number becomes makable.


You can do this the other way around, of course:

   0000000000111111111122222222223333333333444444444455555555556666666666
   0123456789012345678901234567890123456789012345678901234567890123456789
   X       X       X       X       X       X       X       X       X
        X       X       X       X       X       X       X       X       X
             X       X       X       X       X       X       X       X
                  X       X       X       X       X       X       X
                       X       X       X       X       X       X       X
                            X       X       X       X       X       X
   X    X  X X  X XX X XX XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

This is starting with the multiplies of 8, and then shifting each row 5 
to the right. It produces the exact same pattern, obviously.

I have yet to determine why 27 is the last unmakable number. It seems to 
sit suspiciously close to 25, though. In the table above, the final row 
starts at 25. Alternatively, in the previous table, the last row starts 
at 32, and 27 is near to 32 as well...

Post a reply to this message