Warp's challenge on prime numbers got me thinking...

The product of two integers is always an integer. However, the quotient 
is not always an integer. When it is, we say that the integers are 
"divisible". This idea leads directly to the concepts of "factors" and 
"divisors", and eventually to the "prime numbers". Famously, every 
natural number is uniquely expressible as a product of prime numbers.

Addition has no such properly. For any given integer, there are an 
unlimited number of integer sums which produce it. And that's because 
unlike a quotient, the difference between two integers /is/ always an 
integer.

Looking back at multiplication again, suppose we move from the integers 
to the rationals. Now suddenly the concept of divisibility goes away. 
/Every/ rational is "divisible" by /every/ other rational. (With the 
exception of zero, anyway.) All the interesting structure has 
disappeared. (Unless we continue to treat the integers as a "special" 
subset of the rationals...)

To summarise: Multiplication has an interesting structure in the 
integers, but that structure goes away when we consider a larger set 
(the rationals).

Addition does not have an interesting structure on the integers. 
Question: Is there some subset of the integers which /would/ have a 
similar, interesting structure?



It turns out you /can/ actually do this. And since it can be done, 
unsurprisingly various mathematicians have done it. There's even a term 
for it: It's called a numerical monoid.

According to Jumanji, "In the jungle you must wait, 'till the dice read 
five or eight."

So, what happens if we start with the only integers being 5 and 8. What 
other integers can we produce by adding these?

   5 + 5 = 10
   5 + 8 = 13
   5 + 5 + 5 = 15
   8 + 8 = 16
   5 + 5 + 8 = 18
   5 + 5 + 5 + 5 = 20
   5 + 8 + 8 = 21
   5 + 5 + 5 + 8 = 23
   8 + 8 + 8 = 24
   ...

In particular, there is no way of making 27, but you can make 28 just 
fine (5+5+5+5+8). Actually,

   28 = 5+5+5+5+8
   29 = 5+8+8+8
   30 = 5+5+5+5+5+5
   31 = 5+5+5+8+8
   32 = 8+8+8+8
   33 = 5+5+5+5+5+8
   34 = 5+5+8+8+8

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

When you get to 40, something interesting happens. For 5*8 = 40, which 
means that we have

   5*8 = 5+5+5+5+5+5+5+5 = 40
   8*5 = 8+8+8+8+8       = 40

So this number can be made in /two/ different ways.

When we come to 45, the same happens again, since 45 = 40+5, and 40 
itself can be made two different ways. So you can take both of those 
ways and append +5 to make 45 in two different ways.

The same happens again with 48 = 40+8.

It happens yet again with 50 = 40+10. 10 can only be made one way, but 
40 has two ways.

It happens yet again with 13, since 53 = 40+13, and 13 is makable.

In fact, above 27, /every/ number can be made at least one way, 40 is 
the first number that can be made /two/ ways, and every number which can 
be made by adding a makable number to 40 also has two ways.

In this way, the 1-makable numbers start of rare and get denser, until 
we get to 20, the first 2-makable number. The 2-makables get denser in 
the same pattern, until at 80 ( = 40 + 40) we get the first 4-makable 
number.

(At this point, the Haskell interpreter died when I tried to feed it 
with larger numbers. I need to go code a better algorithm...)



There's an interesting paper about it here:

   http://www.shsu.edu/~stc008/Knoxvillemaintalk2007.pdf

Figure 1 is really epic, by the way.

Wikipedia has this to say:

   http://en.wikipedia.org/wiki/Numerical_semigroup

Post a reply to this message