tag:blogger.com,1999:blog-9319479.post2548414329179389517..comments2024-03-07T15:32:53.014+02:00Comments on Yehuda: Number Spanning Using Sets of Natural NumbersYehuda Berlingerhttp://www.blogger.com/profile/16038826060312027387noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-9319479.post-39521616163376411202007-09-23T18:05:00.000+02:002007-09-23T18:05:00.000+02:00I think I need a drink.YehudaI think I need a drink.<BR/><BR/>YehudaYehuda Berlingerhttps://www.blogger.com/profile/16038826060312027387noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-23948859878357809062007-09-23T17:59:00.000+02:002007-09-23T17:59:00.000+02:00Ok, here is a definite proof:Let n_i be the initia...Ok, here is a definite proof:<BR/><BR/>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.<BR/><BR/>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)<BR/><BR/>In the last sum all the coefficients are positive.<BR/><BR/>So beyond (n_1-1)*P0 all numbers can be written as natural sums. There may be a smaller number with that property.David Kleinhttps://www.blogger.com/profile/06755024284475081837noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-87567781672642965122007-09-23T17:12:00.000+02:002007-09-23T17:12:00.000+02:00I agree, way too fuzzym to the extent that I am no...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 :-(David Kleinhttps://www.blogger.com/profile/06755024284475081837noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-18518613547116841482007-09-23T17:06:00.000+02:002007-09-23T17:06:00.000+02:00I guess that makes some sense, although it's fairl...I guess that makes some sense, although it's fairly fuzzy. Is there any way of finding that number P?<BR/><BR/>YehudaYehuda Berlingerhttps://www.blogger.com/profile/16038826060312027387noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-40463792048296008022007-09-23T16:57:00.000+02:002007-09-23T16:57:00.000+02:00I didn't make it explicit, but you can always add ...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.David Kleinhttps://www.blogger.com/profile/06755024284475081837noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-66153132679966416272007-09-23T16:29:00.000+02:002007-09-23T16:29:00.000+02:00You're talking about integers, while I'm talking a...You're talking about integers, while I'm talking about natural numbers.<BR/><BR/>YehudaYehuda Berlingerhttps://www.blogger.com/profile/16038826060312027387noreply@blogger.comtag:blogger.com,1999:blog-9319479.post-63854944160832764942007-09-23T16:17:00.000+02:002007-09-23T16:17:00.000+02:00For any finite set of integers, {n1, n2, ...} a nu...For any finite set of integers, {n1, n2, ...} a number K can be<BR/>written as a sum m1*n1+m2*n2+... with integer m1, m2, ... if and only<BR/>if K is a multiple of the gcd (Greatest Commond Divisor) of the n's.<BR/>(See e.g. WikiPedia)<BR/><BR/>So all numbers beyond a certain point can be written as a sum of the<BR/>n's if and only if their gcd is one.<BR/><BR/>BTW, there is an open conjecture in mathematics as follows:<BR/><BR/>The only decomposition of the integers into m>=3 sequences<BR/>{[a_i*n+b_i]} where n ranges over the integers, a_i and b_i are any<BR/>real numbers, all a_i>0 and distinct is given by<BR/><BR/>{a_1, ..., a_m} = {(2^m-1)/2^k for k in [0,m)}<BR/><BR/>See for example <A HREF="http://www.math.leidenuniv.nl/~tijdeman/tij2.ps" REL="nofollow">here</A>.<BR/><BR/>This is known as the Fraenkel conjecture (better known around our<BR/>house as "Saba").David Kleinhttps://www.blogger.com/profile/06755024284475081837noreply@blogger.com