Saturday, September 22, 2007

Number Spanning Using Sets of Natural Numbers

Yom Kippur is a day of atonement, fasting, and prayer. One enters the synagogue at 7 or 8 in the morning, and aside from a brief break before the afternoon service for around 2 hours (if you're lucky), you don't leave until nightfall.

Occasionally in the service there is some mental downtime, which is when I came up with this ...

Natural Number Spanning

Spanning with 1

The number 1 can be used to make any natural number (defined as excluding 0) though addition. N = 1 + 1 + 1 ... N times. Or simply N = 1*N.

So any set of two or more numbers (e.g. {n,m}) can be combined some number of times to make any natural number if one of the numbers is 1. You simply ignore all the other numbers in the set.

Spanning with 2

Let's say you don't have 1 in your set. The simplest set is {2,3}. Can this set S be used to make any natural number greater than 1? Yes.

Proof: The number 2 can be used to make any even number 2, 4, 6, ... And odd number can be created using 3 plus an even number.

Using a similar proof, it is possible to make any natural number of N or greater, if N is an odd number, either with a series of 2's or the number N plus a series of 2s.

The set {2, N} where N is an even number cannot be used to create any odd numbers.

Spanning with 3 and 4

What about the set {3,4}? The number 4 can be used to create every second even number. Furthermore, two 3's make 6; add 4's to this to get the remaining even numbers. Use 3 plus one of these numbers to get all odd numbers, except for the number 5.

Spanning with other sets

The question is: Given the set {m,n}: n > m. Is there a number P such that for all numbers P or greater you can combine multiples of m and n to create that number? How many numbers between n and P can't be so created?

I would be surprised if this wasn't already explored somewhere in mathematical theory. It's king of like using polyominoes to cover a plain or a chessboard.

A related mathematical subject is Bézout's identity for relative primes.

Post a Comment