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.
Yehuda
7 comments:
For any finite set of integers, {n1, n2, ...} a number K can be
written as a sum m1*n1+m2*n2+... with integer m1, m2, ... if and only
if K is a multiple of the gcd (Greatest Commond Divisor) of the n's.
(See e.g. WikiPedia)
So all numbers beyond a certain point can be written as a sum of the
n's if and only if their gcd is one.
BTW, there is an open conjecture in mathematics as follows:
The only decomposition of the integers into m>=3 sequences
{[a_i*n+b_i]} where n ranges over the integers, a_i and b_i are any
real numbers, all a_i>0 and distinct is given by
{a_1, ..., a_m} = {(2^m-1)/2^k for k in [0,m)}
See for example here.
This is known as the Fraenkel conjecture (better known around our
house as "Saba").
You're talking about integers, while I'm talking about natural numbers.
Yehuda
I didn't make it explicit, but you can always add a large enough multiple of the LCM (Least Common Multiple) to make all the m's positive. The conclusion remains the same for natural numbers (which is what I stated in the 2nd paragraph. All numbers beyond a certain point can be written as a *SUM* of the n's if and only if their gcd is one.
I guess that makes some sense, although it's fairly fuzzy. Is there any way of finding that number P?
Yehuda
I agree, way too fuzzym to the extent that I am no longer even positive I am correct. I will check my math in detail, and probably come up with a value for P (or a counter example :-(
Ok, here is a definite proof:
Let n_i be the initial numbers. If their gcd is not 1, then even using integers you can't reach all natural numbers, so we must have gcd=1. So sum a_i*n_i = 1. In order to distinguish positive and negative coefficients, let's write this as sum b_i*n_i - sum (c_i*n_i) where b_i and c_i are all natural numbers (or zero). Let P0 = sum (c_i*n_i). Then any number greater than P = (n_1-1)*P0 can be written as a sum with non-negative coefficients.
Proof: If N>P then N = P + k*n_1 + r where k is non-negative and 0 <= r < n_1 is the remainder. But then k*n_1 + r + P = k*n_1 + r*sum(b_i*n_i) - r*sum(c_i*n_i) + P = k*n_1 + r*sum b_i*n_i) - r*sum(c_i*n_i) + (n_1-1)*sum(c_i*n_i) = k*n_1 + r*sum b_i*n_i) + sum((n_1-1-r)*c_i*n_i)
In the last sum all the coefficients are positive.
So beyond (n_1-1)*P0 all numbers can be written as natural sums. There may be a smaller number with that property.
I think I need a drink.
Yehuda
Post a Comment