Every integer >=, 34, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 0 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 34, and <=, 105 Proof: Routine (left to the reader). Since there are, 71, integers to check (\ we did it!), just for the sake of illustration let's pick three random i\ ntegers >=, 34, and , 105 For the integer, 78, There are , 4, such representations, let us only list, 1, of them (after all that is all we need) {{11}} For the integer, 39, There are , 3, such representations, let us only list, 1, of them (after all that is all we need) {{1, 7}} For the integer, 92, There are , 14, such representations, let us only list, 1, of them (after all that is all we need) {{0, 12}} We will now prove that if the integer y is larger than, 105, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 34, and <, y, and we will prove that it is also true for y Since p(j), j>=, 0, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 105, this N is >=, 12 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 34 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 34, for N >=, 12 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 12, is , 12 since the value of p(n) at n=, 12, is , 105 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 51, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 1 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 51, and <=, 210 Proof: Routine (left to the reader). Since there are, 159, integers to check \ (we did it!), just for the sake of illustration let's pick three random \ integers >=, 51, and , 210 For the integer, 94, There are , 11, such representations, let us only list, 1, of them (after all that is all we need) {{1, 12}} For the integer, 150, There are , 13, such representations, let us only list, 1, of them (after all that is all we need) {{8, 13}} For the integer, 88, There are , 5, such representations, let us only list, 1, of them (after all that is all we need) {{3, 11}} We will now prove that if the integer y is larger than, 210, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 51, and <, y, and we will prove that it is also true for y Since p(j), j>=, 1, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 210, this N is >=, 18 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 51 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 51, for N >=, 18 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 18, is , 18 since the value of p(n) at n=, 18, is , 210 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 114, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 2 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 114, and <=, 861 Proof: Routine (left to the reader). Since there are, 747, integers to check \ (we did it!), just for the sake of illustration let's pick three random \ integers >=, 114, and , 861 For the integer, 310, There are , 68, such representations, let us only list, 1, of them (after all that is all we need) {{3, 23}} For the integer, 396, There are , 152, such representations, let us only list, 1, of them (after all that is all we need) {{8, 25}} For the integer, 465, There are , 280, such representations, let us only list, 1, of them (after all that is all we need) {{29}} We will now prove that if the integer y is larger than, 861, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 114, and <, y, and we will prove that it is also true for y Since p(j), j>=, 2, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 861, this N is >=, 39 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 114 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 114, for N >=, 39 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 39, is , 39 since the value of p(n) at n=, 39, is , 861 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 119, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 3 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 119, and <=, 903 Proof: Routine (left to the reader). Since there are, 784, integers to check \ (we did it!), just for the sake of illustration let's pick three random \ integers >=, 119, and , 903 For the integer, 135, There are , 2, such representations, let us only list, 1, of them (after all that is all we need) {{4, 14}} For the integer, 862, There are , 2175, such representations, let us only list, 1, of them (after all that is all we need) {{4, 25, 30}} For the integer, 859, There are , 2112, such representations, let us only list, 1, of them (after all that is all we need) {{7, 14, 36}} We will now prove that if the integer y is larger than, 903, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 119, and <, y, and we will prove that it is also true for y Since p(j), j>=, 3, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 903, this N is >=, 40 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 119 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 119, for N >=, 40 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 40, is , 40 since the value of p(n) at n=, 40, is , 903 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 174, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 4 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 174, and <=, 1891 Proof: Routine (left to the reader). Since there are, 1717, integers to check\ (we did it!), just for the sake of illustration let's pick three random\ integers >=, 174, and , 1891 For the integer, 936, There are , 1730, such representations, let us only list, 1, of them (after all that is all we need) {{7, 14, 38}} For the integer, 1359, There are , 14253, such representations, let us only list, 1, of them (after all that is all we need) {{20, 46}} For the integer, 1471, There are , 21818, such representations, let us only list, 1, of them (after all that is all we need) {{4, 11, 51}} We will now prove that if the integer y is larger than, 1891, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 174, and <, y, and we will prove that it is also true for y Since p(j), j>=, 4, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 1891, this N is >=, 59 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 174 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 174, for N >=, 59 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 59, is , 59 since the value of p(n) at n=, 59, is , 1891 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 214, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 5 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 214, and <=, 2775 Proof: Routine (left to the reader). Since there are, 2561, integers to check\ (we did it!), just for the sake of illustration let's pick three random\ integers >=, 214, and , 2775 For the integer, 1417, There are , 8937, such representations, let us only list, 1, of them (after all that is all we need) {{12, 50}} For the integer, 525, There are , 59, such representations, let us only list, 1, of them (after all that is all we need) {{5, 16, 25}} For the integer, 1408, There are , 8471, such representations, let us only list, 1, of them (after all that is all we need) {{6, 13, 49}} We will now prove that if the integer y is larger than, 2775, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 214, and <, y, and we will prove that it is also true for y Since p(j), j>=, 5, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 2775, this N is >=, 72 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 214 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 214, for N >=, 72 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 72, is , 72 since the value of p(n) at n=, 72, is , 2775 we are safe. QED. ---------------------------------------------------------------------- Every integer >=, 224, can be represented in at least, 1, (j + 1) (j + 2) different ways as sum of DISTINCT integer values of, ---------------, 2 with j>=, 6 By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) Theorem: See title Proof: we first need a lemma Lemma: The statement of the theorem is true for all n >=, 224, and <=, 3003 Proof: Routine (left to the reader). Since there are, 2779, integers to check\ (we did it!), just for the sake of illustration let's pick three random\ integers >=, 224, and , 3003 For the integer, 1842, There are , 25673, such representations, let us only list, 1, of them (after all that is all we need) {{35, 47}} For the integer, 1272, There are , 2547, such representations, let us only list, 1, of them (after all that is all we need) {{8, 32, 35}} For the integer, 2873, There are , 614794, such representations, let us only list, 1, of them (after all that is all we need) {{33, 66}} We will now prove that if the integer y is larger than, 3003, there always at least, 1, such representations. The proof is by induction\ on y. Assume that the statement is true for all integers >=, 224, and <, y, and we will prove that it is also true for y Since p(j), j>=, 6, is an increasing sequence there is a unique integer, let\ 's call it N such that p(N)=, 3003, this N is >=, 75 We express y as y= (y-p(N-3))+p(N-3) We claim that (i): y-p(N-3)>=, 224 (ii): y-p(N-3)p(N)-p(N-3)=, 3 N But this is >=, 224, for N >=, 75 To prove (ii) note that since y<=p(N+1) y-p(N-3) <= p(N+1)-p(N-3)=, 12 The larger of these cutoffs integers, 12, 75, is , 75 since the value of p(n) at n=, 75, is , 3003 we are safe. QED.