 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/08/2012 11:15 AM, Invisible wrote:
> 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.
Actually, no.
There are two ways to make 40: 5*8 and 8*5. That means you might /think/
there should be 4 ways to make 80:
5*8 + 5*8
5*8 + 8*5
8*5 + 5*8
8*5 + 8*5
The thing is, the middle two are equivalent. (Assuming we're ignoring
ordering.) One is five 8s plus eight 5s, and the other is the same
thing, but in a different order. So actually, 80 is only 3-makable.
120 is the first 4-makable number, being 40 + 40 + 40. (Then 125, then
128, then 130, etc.) The first 5-makable number is 160 ( = 4*40).
So it seems that there's a pattern at the bottom where certain numbers
can be made and certain others can't. 5*8 = 40 is the first 2-makable
number, and the pattern repeats every 40 numbers or so.
In short, numbers less than 40 are either impossible, or can be uniquely
expressed as a sum of 5s and 8s. Above 40, the representation stops
being unique. (40 has two distinct expressions, and in generate n*40 has
n+1 unique expressions.) So it's not quite like with prime numbers,
where integers can be /uniquely/ factorised into primes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 09/08/2012 12:15, Invisible a écrit :
> 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.
Actually there is a conjecture about the sum:
every even number greater than 2 is the sum of two prime numbers.
(Goldbach 's conjecture)
every odd number is at most the sum of three prime numbers.
(easy: add any odd prime to an even number... if you can prove Goldbach!)
So, every positive number is the sum of at most three prime numbers.
On similar lines, every positive integers integer is the sum of 4
squares. (Lagrange, proven).
Another conjecture: Every large odd number (n > 5) is the sum of a prime
and the double of a prime.
Caveat about defining prime number, the definition might or not include
1. (holy war predicted...)
(notice that Goldbach does not state if the sum is unique: it is not. 18
= 13+5 = 11+7)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
It's perhaps even clearer if I do it with 5 and 6. Obviously 6 is one
greater than 5, which means that each row is 1 step out of sync with the
previous one.
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 XXX XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
By the time we get to the right, the pattern /obviously/ covers all
possible numbers. Actually we only need to go 5 steps right for this to
happen.
At each repartition the number 5n-1 is unmakable. This stops being the
case on the final repartition. So the last number which /is/ unmakable
exists on the previous repartition. That is,
5*4 - 1
which is 19. If you check the table above, you see that this is correct.
Going back to 5 and 8, it's not quite clear how this number comes up.
Wikipedia asserts that the largest unmakable number is called the
"Frobenius number", and that for a system with two initial integers A
and B, the Frobenius number is always
(A - 1)(B - 1) - 1
In the case of 5 and 8, that gives us 4*7-1 which is indeed 27.
Wikipedia also claims that the /total/ number of unmakable numbers is
(A - 1)(B - 1) / 2
For the <5, 6> case, that's 4*5/2 = 10, which is indeed correct.
Apparently there is no known formula for the case of more than two
integers...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9-8-2012 12:15, Invisible wrote:
> 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.
Does that make 67 the highest number you can make in only one way?
--
Women are the canaries of science. When they are underrepresented
it is a strong indication that non-scientific factors play a role
and the concentration of incorruptible scientists is also too low
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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.
>
> Does that make 67 the highest number you can make in only one way?
Yes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8/9/2012 1:31 PM, andrel wrote:
> On 9-8-2012 12:15, Invisible wrote:
>> Warp's challenge on prime numbers got me thinking...
>>
>> 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.
>
> Does that make 67 the highest number you can make in only one way?
If you generalize to allow the factors of 8 and 5 to be negative
integers, then every integer can be made an infinite number of different
ways.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
