[math-fun] Subset Problem
If we let S be a set of n integers, then how can we determine the lowest number x_k such that x_k is a sum of 1, 2, 3, ..., k distinct elements of S? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com
At 11:09 PM 1/8/04 +0000, you wrote:
If we let S be a set of n integers, then how can we determine the lowest number x_k such that x_k is a sum of 1, 2, 3, ..., k distinct elements of S?
I must not be understanding the problem. What is wrong with simply adding up the k smallest elements of S? -A
I think he wants the number to be the sum of 1 distinct element, 2 distinc elements, 3 distinct elements,,..., and k distinct elements. Just because a,b \in S does not imply a+b \in S. So, just because k+1 distinct elements of S add up to something doesn't not mean k elements of S add up to something. For example there is no number which is the of both 2 and 1 distinct elements of {1,2,4,8,16} or the subset of any other geometric progression for that matter. You can just get the sets of elements that are the sum 1 distinct elments, 2 distinct elements, ..., and take their interesection. If all of the integers in S are positive, then you can order them, and see if S_m+S_m+1+..S_m+k<S_(m+k+1) for all positive integers m with a fixed k in which case you could easily prove that there are no numbers such that 1,2,3,...,k distinct elements of S sum up to a given number. It might be interesting let S be the set of primes, and consider Perry's question. 5=2+3 19=17+2, 11+5+3 31=29+2, 23+5+3, 19+7+3+2 43=41+2, 31+7+5, 29+7+5+2, 17+11+7+5+3 61=59+2, 31+19+11, 31+17+11+2, 23+19+11+5+3, 23+17+11+5+3+2 73=71+2, 61+7+5, 59+7+5+2, 31+19+11+7+5, 31+19+11+7+3+2 Note: I just found these by hand If p is (k-1)'th number satisfying i) p is prime ii) p does not equal 7 iii) p=q+2 where q is prime then is p always equal to the sum of n distinct primes where n<=k? Are the representations as sums of k primes unique? I think generalizations of these thing could relate to quesitons like how many solutions are there to the equations p+q=r+s for p,q,r,s distinct primes? Gershon Bialer ----- Original Message ----- From: "Allan C. Wechsler" <acw@alum.mit.edu> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Sunday, January 11, 2004 4:55 PM Subject: Re: [math-fun] Subset Problem
At 11:09 PM 1/8/04 +0000, you wrote:
If we let S be a set of n integers, then how can we determine the lowest number x_k such that x_k is a sum of 1, 2, 3, ..., k distinct elements of S?
I must not be understanding the problem. What is wrong with simply adding up the k smallest elements of S? -A
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This interpretation is correct; '5=2+3 19=17+2, 11+5+3 31=29+2, 23+5+3, 19+7+3+2 43=41+2, 31+7+5, 29+7+5+2, 17+11+7+5+3 61=59+2, 31+19+11, 31+17+11+2, 23+19+11+5+3, 23+17+11+5+3+2 73=71+2, 61+7+5, 59+7+5+2, 31+19+11+7+5, 31+19+11+7+3+2' although 73 as listed has only 6 distinct primes, and to qualify requires 7; Two other interesting sets of integers are the Fibonacci numbers and the Partition numbers. With Fibonacii, let a_1=1 and a_2=1, and these are distinct, so: 2=1+1 5=3+2=3+1+1 13=8+5=8+3+2=8+3+1+1 34=21+13=21+8+5=21+8+3+2=21+8+3+1+1 so there is an obvious pattern here. The Partition numbers seem to behave as if they avoid being the sum of 2 distinct previous elements (we can even drop the distinct part) after 30. Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com -----Original Message----- From: math-fun-bounces+perry=globalnet.co.uk@mailman.xmission.com [mailto:math-fun-bounces+perry=globalnet.co.uk@mailman.xmission.com]On Behalf Of Gershon Bialer Sent: 12 January 2004 00:30 To: math-fun Subject: Re: [math-fun] Subset Problem I think he wants the number to be the sum of 1 distinct element, 2 distinc elements, 3 distinct elements,,..., and k distinct elements. Just because a,b \in S does not imply a+b \in S. So, just because k+1 distinct elements of S add up to something doesn't not mean k elements of S add up to something. For example there is no number which is the of both 2 and 1 distinct elements of {1,2,4,8,16} or the subset of any other geometric progression for that matter. You can just get the sets of elements that are the sum 1 distinct elments, 2 distinct elements, ..., and take their interesection. If all of the integers in S are positive, then you can order them, and see if S_m+S_m+1+..S_m+k<S_(m+k+1) for all positive integers m with a fixed k in which case you could easily prove that there are no numbers such that 1,2,3,...,k distinct elements of S sum up to a given number. It might be interesting let S be the set of primes, and consider Perry's question. 5=2+3 19=17+2, 11+5+3 31=29+2, 23+5+3, 19+7+3+2 43=41+2, 31+7+5, 29+7+5+2, 17+11+7+5+3 61=59+2, 31+19+11, 31+17+11+2, 23+19+11+5+3, 23+17+11+5+3+2 73=71+2, 61+7+5, 59+7+5+2, 31+19+11+7+5, 31+19+11+7+3+2 Note: I just found these by hand If p is (k-1)'th number satisfying i) p is prime ii) p does not equal 7 iii) p=q+2 where q is prime then is p always equal to the sum of n distinct primes where n<=k? Are the representations as sums of k primes unique? I think generalizations of these thing could relate to quesitons like how many solutions are there to the equations p+q=r+s for p,q,r,s distinct primes? Gershon Bialer ----- Original Message ----- From: "Allan C. Wechsler" <acw@alum.mit.edu> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Sunday, January 11, 2004 4:55 PM Subject: Re: [math-fun] Subset Problem
At 11:09 PM 1/8/04 +0000, you wrote:
If we let S be a set of n integers, then how can we determine the lowest number x_k such that x_k is a sum of 1, 2, 3, ..., k distinct elements of S?
I must not be understanding the problem. What is wrong with simply adding up the k smallest elements of S? -A
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jon Perry wrote
If we let S be a set of n integers, then how can we determine the lowest number x_k such that x_k is a sum of 1, 2, 3, ..., k distinct elements of S?
Gershon Bialer wrote
It might be interesting [to] let S be the set of primes, and consider Perry's question. 5=2+3 19=17+2, 11+5+3 31=29+2, 23+5+3, 19+7+3+2 43=41+2, 31+7+5, 29+7+5+2, 17+11+7+5+3 61=59+2, 31+19+11, 31+17+11+2, 23+19+11+5+3, 23+17+11+5+3+2 ... Note: I just found these by hand
I just found these by computer. 2 5 3+2 19 17+2 11+5+3 31 29+2 23+5+3 19+7+3+2 43 41+2 31+7+5 31+7+3+2 17+11+7+5+3 61 59+2 53+5+3 47+7+5+2 29+17+7+5+3 31+13+7+5+3+2 103 101+2 89+11+3 89+7+5+2 71+17+7+5+3 73+13+7+5+3+2 47+17+13+11+7+5+3 103 the above, and 43+19+13+11+7+5+3+2 139 137+2 131+5+3 127+7+3+2 113+11+7+5+3 109+13+7+5+3+2 83+17+13+11+7+5+3 79+19+13+11+7+5+3+2 41+23+19+17+13+11+7+5+3 151 149+2 139+7+5 139+7+3+2 113+23+7+5+3 113+17+11+5+3+2 89+23+13+11+7+5+3 83+23+17+11+7+5+3+2 53+23+19+17+13+11+7+5+3 43+31+19+17+13+11+7+5+3+2 199 197+2 191+5+3 181+13+3+2 173+11+7+5+3 163+19+7+5+3+2 137+23+13+11+7+5+3 139+19+13+11+7+5+3+2 101+23+19+17+13+11+7+5+3 89+29+23+17+13+11+7+5+3+2 41+31+29+23+19+17+13+11+7+5+3 229 227+2 211+13+5 211+13+3+2 197+17+7+5+3 199+13+7+5+3+2 173+17+13+11+7+5+3 163+19+17+13+7+5+3+2 131+23+19+17+13+11+7+5+3 113+29+23+19+17+11+7+5+3+2 71+31+29+23+19+17+13+11+7+5+3 61+37+31+23+19+17+13+11+7+5+3+2 283 281+2 271+7+5 271+7+3+2 257+11+7+5+3 241+19+13+5+3+2 227+17+13+11+7+5+3 223+19+13+11+7+5+3+2 179+29+19+17+13+11+7+5+3 173+29+23+17+13+11+7+5+3+2 113+43+29+23+19+17+13+11+7+5+3 113+41+29+23+19+17+13+11+7+5+3+2 47+41+37+31+29+23+19+17+13+11+7+5+3 313 311+2 293+17+3 293+13+5+2 281+17+7+5+3 283+13+7+5+3+2 257+17+13+11+7+5+3 241+31+13+11+7+5+3+2 199+29+23+19+17+11+7+5+3 199+37+19+17+13+11+7+5+3+2 149+37+29+23+19+17+13+11+7+5+3 139+43+31+23+19+17+13+11+7+5+3+2 71+47+37+31+29+23+19+17+13+11+7+5+3 73+43+37+31+29+23+19+17+13+11+7+5+3+2 421 419+2 409+7+5 409+7+3+2 389+17+7+5+3 383+17+11+5+3+2 359+23+13+11+7+5+3 353+23+17+11+7+5+3+2 317+29+19+17+13+11+7+5+3 313+31+19+17+13+11+7+5+3+2 263+31+29+23+19+17+13+11+7+5+3 251+41+29+23+19+17+13+11+7+5+3+2 179+47+37+31+29+23+19+17+13+11+7+5+3 181+43+37+31+29+23+19+17+13+11+7+5+3+2 89+53+43+41+37+31+29+23+19+17+13+11+7+5+3 421 the above, and 83+53+47+41+37+31+29+23+19+17+13+11+7+5+3+2 523 521+2 509+11+3 509+7+5+2 491+17+7+5+3 487+19+7+5+3+2 467+17+13+11+7+5+3 463+19+13+11+7+5+3+2 419+29+19+17+13+11+7+5+3 409+37+19+17+13+11+7+5+3+2 359+37+29+23+19+17+13+11+7+5+3 353+41+29+23+19+17+13+11+7+5+3+2 281+47+37+31+29+23+19+17+13+11+7+5+3 283+43+37+31+29+23+19+17+13+11+7+5+3+2 197+47+43+41+37+31+29+23+19+17+13+11+7+5+3 181+61+43+41+37+31+29+23+19+17+13+11+7+5+3+2 83+61+53+47+43+41+37+31+29+23+19+17+13+11+7+5+3 523 the above, and 83+59+53+47+43+41+37+31+29+23+19+17+13+11+7+5+3+2 For Dr. Sloane's benefit, %I A000000 %S A000000 2,5,19,31,43,61,103,103,139,151,199,229,283,313,421,421,523,523 %N A000000 a(n) is the least number which is the "sum" of 1 prime, the sum of 2 distinct primes, the sum of 3 distinct primes, ..., and the sum of n distinct primes. %e A000000 a(5)=43 because 43=41+2=31+7+5=31+7+3+2=17+11+7+5+3 %K A000000 nonn %O A000000 1,1 %A A000000 Jon Perry (perry(AT)globalnet.co.uk), Gershon Bialer (gersh(AT)bialer.com), Jan 11 2004 -- Don Reble djr@nk.ca
participants (4)
-
Allan C. Wechsler -
Don Reble -
Gershon Bialer -
Jon Perry