- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The Tarry-Escott problem
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The Tarry-Escott problem 1965
pdf
Page Metadata
Item Metadata
Title | The Tarry-Escott problem |
Creator |
Barrodale, Ian |
Publisher | University of British Columbia |
Date Created | 2011-09-14T23:59:54Z |
Date Issued | 2011-09-14 |
Date | 1965 |
Description | The numbers 1, 2, and 6 have the same sum and same sum of squares as 0, 4, 5. These two sets are solutions of degree 2 of the Tarry-Escott problem. This problem of finding sets of integers having equal sums of like powers has been investigated for at least two hundred years and we have presented most of the general results. For any given k there exist solutions in integers of the system of equations (formula omitted) any solution will be composed of a set and a permutation of the set; such solutions are called trivial. Many writers have attempted to provide non-trivial solutions for the optimum case where s = k + 1. These so called ideal solutions exist for all k≦9 but no such solutions have been found for k≧10. We have been interested in providing solutions where s is smaller than for previous known examples, and have generated such solutions using a digital computer. Some of our results also apply to an extension of the Tarry-Escott problem in view of a result concerning bounds for this problem. |
Subject |
Number Theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | Eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project [http://www.library.ubc.ca/archives/retro_theses/] |
Date Available | 2011-09-14T23:59:54Z |
DOI | 10.14288/1.0080617 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/37345 |
Aggregated Source Repository | DSpace |
Digital Resource Original Record | https://open.library.ubc.ca/collections/831/items/1.0080617/source |
Download
- Media
- UBC_1965_A8 B2.pdf [ 1.41MB ]
- Metadata
- JSON: 1.0080617.json
- JSON-LD: 1.0080617+ld.json
- RDF/XML (Pretty): 1.0080617.xml
- RDF/JSON: 1.0080617+rdf.json
- Turtle: 1.0080617+rdf-turtle.txt
- N-Triples: 1.0080617+rdf-ntriples.txt
- Citation
- 1.0080617.ris
Full Text
THE TARRY-ESCOTT PROBLEM by N I A N BARRODALE B . S c , University of Wales, 1960 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS in the Department of MATHEMATICS We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA JUNE, 1965 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r - m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s v I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i - c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date o7.°t "" xJu-M^ ABSTRACT The numbers 1, 2, and 6 have the same sum and same sum of squares as 0, 4, 5. These two sets are solutions of degree 2 of the Tarry-Escott problem. This problem of finding sets of integers having equal sums of . like powers has been investigated for at least two hundred years and we have presented most of the general results. For any given k there exist solutions in integers of the system of s . s . equations ^ = ^ b^ (j = 1, 2, k) for s |5 k + 1. i=l i=l If s.<= k + 1 any solution will be composed of a set and a permutation of the set; such solutions are called t r i v i a l . Many writers have attempted to provide non-trivial solutions for the optimum case where s = k + 1. These so called ideal solutions exist for a l l k S 9 but no such solutions have been found for k §=10. We have been interested in providing solutions where s is smaller than for previous known examples, and have generated such solutions using a digital computer. Some of our results also apply to an extension of the Tarry-Escott problem in view of a result concerning bounds for this problem. TABLE OF CONTENTS TITLE . . . . . . i ABSTRACT . . . . . . . . . i i LIST OF TABLES . . iv LIST OF FIGURES v ACKNOWLEDGEMENTS vi I. THE NATURE OF THE PROBLEM 1. Introduction 1 2. Existence of Solutions 2 3. Ideal Solutions 4 II. , SOME RECENT RESULTS 1. Bounds for N(k) 6 2. Smallest solutions for certain degrees 11 3. Sequences of ideal solutions . . . . 13 4. An extension of the problem . . . . 14 BIBLIOGRAPHY . . . 16 APPENDICES I. DATA FOR TABLE II 17 II. GENERATING SOLUTIONS BY COMPUTER . . 18 i i i LIST OF TABLES TABLE I . •'. " 8 TABLE II 1 1 TABLE III 1 2 •I _ r iv LIST OF FIGURES FIGURE 1 9 FIGURE 2 . . . . 10 FIGURE 3 . . . . . . . . 18 v ACKNOWLEDGEMENTS I wish to thank my advisor, Dr. Z. A. Melzak, for his suggestions and helpful criticisms. I am grateful to the University of Victoria and the National Research Council for the financial aid provided. Thanks are also due to Mrs. M. Peters of the University of Victoria who typed the manuscript. vi CHAPTER I THE NATURE OF THE PROBLEM 1. Introduction The Tarry-Escott problem in Diophantine Analysis is to find two sets of integers equal in number such that the integers in each set have the same sum, the same sum of squares, etc., up to and including the same sum of kth powers, i.e. we are to find solutions in integers of the system of equations s s (j - 1,2, k) (A) i - i i=i k A solution of (A) is written a,, a - b,, b and a 1 s 1 s set of integers (a^, a g ; b^, b ) satisfying (A) will be referred to as a set of degree k. A solution of (A) in which the a's are merely a permutation of the b's will be called t r i v i a l ; we are concerned with non- trivial solutions. This problem has attracted the attention of number theorists since the time of Goldbach and Euler who noted (1750-51) that 2 a, b, c, a + b + c = a + b, a + c, b + c, 0. Dickson ĵ 3, Chapter 24 j has given a comprehensive summary of papers on the problem of sets of integers with equal sums of like powers, and i t was at his suggestion in view of the contributions made to this problem by G. Tarry and E. B. Escott that the problem is referred to as the Tarry-Escott problem. 2. 2. Existence of Solutions General parametric solutions of (A) have been found for only a few values of k and s. Dickson ^4, pp.52J has proved that every set (a^, a^j a^ ; b^, b^, b^) of degree 2 is obtained by adding an arbitrary 2 integer to each term of AD, AG + BD, BG = AD + BG, BD, AG (where A,B,D,G can be formed using the proof of this theorem from the set (a^ ; b^)). Dickson Ĵ 4, pp.54-58 j also gives general solutions of (A) for s - 4 and k = 2, and for s = 4 and k = 3. There are numerous particular solutions in both parametric and numerical form: 2, 3, 7 = 1, 5, 6 2 a + c, b + c, 2a + 2b + c = c, 2a + b + c, a + 2b + c 0, 5, 5, 10 = 1, 2, 8, 9 + (23a + 57b), + (40a - 6b), + (17a - 63b) = + (23a - 57b), + (40a + 6b), + (17a + 63b) However in view of the following two theorems we can prove the existence of solutions of (A) for other values of s and k without depending on illustrations. k k Theorem 1. If a^, ...,< a = b^, •••> b g then Mâ + K, ..., Mag + K = Mb.. + K, Mb + K where M, K are arbitrary integers. X S This theorem is due to M. Frolov |̂ 5j and can be proved using the binomial theorem. The theorem allows us to operate on a set (a^, a g ; b^, b g) according to the rules of elementary algebra. If one solution of (A) comes from another through the use of Theorem 1 the two solutions are said to be equivalent. We define distinct solutions as solutions that are not equivalent. From Theorem 1 i t follows that for each solution there is an equivalent one where ^ a i = ^ ^ i = *̂ This equivalent solution has been called the standard form by Escott. Thus in: 0, 11/ 13, 22 = 1, 7, 18, 20 if we multiply by 2 in order to make the sum divisible by four, and then subtract one fourth of this new sum from each term, we have -23,-1, 3, 21 = -21, -9, 13, 17 in standard form. Theorem 2. If a g ; b^, b g) is a set of degree k then for any integer d (a^, a g, bl + d, ..., b g + d ; b ^ b g, al + d, a g + d) is a set of degree k +1 This theorem is due to Tarry. ^ 8 J and can also be proved using the binomial theorem. Theorem 2 allows us to build up a solution for (A) of any desired degree starting from any particular solution of (A). Moreover if we choose d to be the number which occurs most frequently among the differences a. - a. and b. - b. we are then able to remove a good many of \ J. 1 J the terms which occur on both sides of the resulting solution of degree k + 1. To illustrate the power of this theorem we present the following sequence ^6, pp. 331j. 4. d = 3 d = 5 d = 7 d - 8 d - 13 d - 11 0, 3 i 1, 2 0, 4, 5 = 1, 2, 6 0,- 4, 7, 11 = 1, 2, 9, 10 0, 4, 8, 16, 17 » 1, 2, 10, 14, 18 0, 4, 9,17, 22, 26 = 1, 2, 12, 14, 24, 25 0, 4, 9, 15, 26, 27, 37, 38 = 1, 2, 12, 13, 24, 30, 35, 39 0, 4, 9, 23, 27, 41, 46, 50 - 1, 2, 11, 20, 30, 39, 48, 49 3. Ideal solutions A number of writers have been interested in finding the least value of s for which (A) will have solutions for any particular k. The following theorem due to Bastien [ l , pp. 171-172] provides a lower bound for s , and we present a proof for the sake of completeness. Theorem 3. If equations (A) have a non-trivial solution, then s 2 k + 1 Proof. Suppose s S k , then the sets (a^ ; b^) have the same sums of powers from the first to the kth. and hence the same symmetric functions. Hence a,, a and b.., b are roots of the same equation and the V ' s '• 1 s n a's are merely a permutation of the b's. Wr ight Ĵ 9, pp. 26l] has defined a function N(k) as the least k number N such that a^, a^ = b^, b^ has non-trivial solutions. 5 . Theorem 3 states that N(k) = k + 1 and Tarry |^8J gave the first upper bound k - 1 for N(k) by showing that N(k)^ 2 (this result follows immediately from any solution of (A) with s =v 4 and k = 3 together with Theorem 2 ) . It has been conjectured that in fact N(k) = k + 1 , and solutions of (A) with s = k + 1 have been called ideal solutions by Chernick J^2, pp. 626j'who proved that there exists an infinite number of distinct ideal solutions of (A) for every value of k ^ 7 . We have provided examples above of ideal solutions of (A) for k = 1 , 2 , 3 , 4 , 5 , 7 and these together with the following three examples ^ 6 , pp. 332 and 3 3 8 j give Theorem 4 . 0 , 1 8 , 2 7 , . 5 8 , . 6 4 , 8 9 , 101 = 1 , 1 3 , 3 8 , 4 4 , 7 5 , 8 4 , 102 0 , 2 4 , 3 0 , 8 3 , 8 6 , 1 3 3 , 1 5 7 , 1 8 1 , 197 = 1 , 1 7 , 4 1 , 6 5 , 1 1 2 , 1 1 5 , 1 6 8 , 1 7 4 , 198 - 1 2 , - 1 1 8 8 1 , - 2 0 2 3 1 , - 2 0 8 8 5 , t 23738 • = • 4 3 6 , - 1 1 8 5 7 , - 2 0 4 4 9 , - 2 0 6 6 7 , - 2 3 7 5 0 Theorem 4 . N(k) = k + 1 for a l l k = 9 6. CHAPTER II SOME RECENT RESULTS 1. Bounds fo r N(k) The best upper bound so far f o r N(k) i s that due to Wright £9, p p . 2 6 1 j who proved ( y (k 2 + 3) k odd N(k) 2 - W(k) =/ •| ( k 2 + 4) k even In 1961 Melzak j^7, pp.234] gave an exact express ion fo r N(k) when he proved that ' «*> - \ P t \ , s[n:<)(i - ,) k + l] where Q i s the c lass of a l l polynomials whose c o e f f i c i e n t s are in tegers , not a l l zero, and n s r £ p ] ^ |a i | for P = P(x) = ^ a i x 1 i=0 i=0 This express ion does not al low one to compute N(k), but with each estimate fo r N(k) i t leads to so lut ions of (A) with s = N . Melzak found that r e l a t i v e l y low bounds for N(k) r e s u l t from taking P(x) of the form p k n p(x):> \j—r (1 - x J ) P j l [ 1 1 Y. * j l L j= i J L n=l j=0 J where p i s a small po s i t i ve integer and p = 0 or 1. The bounds on N(k) are then of the form k + 1 - P . p . with Q(x) = 1 I (1 - x J ) , J 2 S [ Q < X ) ( 1 " * j > In constructing his table of results Melzak used four multipliers Q(x): '. -1, 1 .-.x, 1 - x2, (1 - x)(l - x 2). He selected the lowest estimate N, for N(k) and showed that k k + 1 < N <= W(k) for 2 = k = 29. We have improved these results slightly and also extended them to a l l k 85. We considered the following multipliers Q(x): 1 - x (1 - x)(l - x 2) 1 2 - X (1 - x)(l - x 3) 1 3 - X (1 - x)(l - x 4) I - X (1 - 2 3 x Z ) ( l - X"*) 1 - 5 - X (1 - x 2 ) ( l - x 4) 1 6 - x (1 - x 3 ) ( l - x 4) 1 7 - X (1 - x)(l - x 2 ) ( l -*3> 1 8 - X (1 - x)(l - x 2 ) ( l -*4> x 2 ) ( l - x 3 ) ( l - x 4) (1 - x)(l - x 3 ) ( l x)(l - x 3 ) ( l - x 4 ) ( l - x 5) a n d n 1 1 (1 - x ) for n = 4, 5, 6, 7. For each Q(x), the expression •- S Q(x) ] f (1 - x J) was evaluated (using an I.B.M. 1620) for 1 ̂ k ̂ 30. It was apparent from k+1 these results that the lowest estimates were given when n Q(x) = ~] \ (1 - x ), where n varies with k. The calculations were then continued for 31 =5 k ̂ 85 with Q(x) = "| |" (1 - x n) where 1^'nS 7. j=l Table I was formed by selecting the lowest estimate for 2 ̂ k S 85 and inserting the value of n relevant to each k. 8. TABLE I k N n k n k k 2 3 , 1' ' 44 588 4 3 4 1 45 . 588 3 4 . 6 1 46 627 4 5 6. 47 644 4 6 10 2 48 742 4 7 12 • 1 49 802 . 4 8 18 1 50 830 4 9 18 1 51 872 4 10 22 1 52 834 4 11 22 1 53 896 .' 5 12 . 30 2 54 958 5 13 32 1 55 1072 5 14 41 1 56 1202 5 15 46 1 57 1206 4 16 58 1 58 1218 4 17 58 1 59 1248 5 18 6.8 .2 60 1270 5 19 74 1 61 1376 5 20 88 2 62 1517 5 21 92 2 . 63 1464 5 22 119 2 64 1694 . 5 23 124 2 65 1750 5 24 118 2 66 1866 5 25 146 2 67 1902 5 26 159 2 68 1990 5 27 166 3. 69 1994 5 28 196 2 70 2120 6 29 198 3 71 2224 6 30 207 2 72 2372 6 31 228 3 73 2618 6 32 274 2 74 2947 . 6 33 258 3 75 2906 6 34 305 3 76 2902 6 35 308 3 77 2822 6 36 344 3 78 2853 6 37 332 . • 3 79 3150 7 38 381 3 80 3386 6 39 402 3 81 3604 7 40 472 3 •82 3903 7 41 462 3 83 4136 . 7 42 525 4 84 4502 7 43 514 3 85 4547 7 9. FIGURE 1 4500J 4000 3500 3000 2500 2000 1500 1000 500 10. Figure lv.is the graph of Table I together with the graph of W(k). It is obvious from Figure!, that while our upper bounds on N(k) are lower than W(k) for 2 ^ k.^ 73, they soon become larger than W(k). Hence i f this method is to give further useful results new multipliers P(x) are needed. Following a suggested result of P. Erdos we attempted to f i t 1-c exp (k ) for some c < 1 to the graph of Table I (see Figure 2.). A reasonable approximation to this graph is given when c = 0.52. •> 4 ln 10 4 ln 10" ln 10' In 10 ln N. FIGURE 2 10 20 30 40 50 60 70 80 11. 2. Smallest solutions for certain degrees. By use of Theorem 2 we attempted to obtain solutions of (A) for k 5r 10 where the number of terms s is less than the estimates N. given — k in Table I. An I.B.M. 1620 was programmed so that it would read a solution of (A) of any reasonable length and degree, and then calculate the difference d that occurs most frequently between any two terms from the same side of this given solution. It would then use d with Theorem 2 to produce a solution of (A) of the next higher degree, and continue in this manner. By considering solutions of (A) of many different lengths and degrees we have found examples of solutions for 10 ̂ k jfj 22 where the number of terms s is less than those given in Table I. Table II gives the value of s corresponding to each value of k; the actual solutions of (A) may be found in the Appendix. TABLE II k 10 11 12 13 14 15 16 17 18 19 20 21 22 s 14 18 24 30 30 30 38 48 58 58 65 80 84 However the following weakness was discovered in the algorithm. It had been assumed that from any particular solution of (A) solutions of higher degree would be generated containing the least number of terms s , so long as the most frequent difference d was used at each step. This assumption was false. When forming Table I the multiplier (1 - x) was used with 11 • . ~\~ f (1 - x J) to produce a solution of (A) where s = 22 for k = 11. • j - l 12. This is equivalent to starting with the solution 0,2= 1, 1 and using Theorem 2 with d = 2,..ll. Using the algorithm with this solution the results shown in Table III were obtained. TABLE I I I k+1 (i - x) i r (1 " * j) .1 2 . 2 2 2 3 . . 3 3 3 . .5'. •••'".'"4 4 4 6 6 5 7 6 6 6 11 8 11 7 9 10 12 .8 13 . 14 . . 18 9 17: 14 18 10 19 18 22 11 24 22 Thus, by a more careful choice of d, the length of solutions can be decreased for k = 6, 1, 8, 9, 10. But for k = 11 this gives a solution of (A) where s =24. This solution is longer than that obtained from a sequence of solutions which were constructed from values of d that were not always the most frequent. 13. 3. Sequences of ideal solutions. I(m,n) was defined to be any sequence of ideal solutions of (A) of each degree from m to n inclusive, that is generated by Theorem 2. Then we indicate the proof of the following Theorem. Theorem 5. 1(1,n) does not exist for n 5r 6 Proof. We need only show that no ideal solution of (A) of degree 6 can be obtained by the use of Theorem 2 from any sequence of ideal solutions of consecutive degrees starting with degree 1. Al l ideal solutions of (A) of degree 1 are equivalent to 0, a = b, c (where b ̂ c). This gives 0, 2b + c, b + 2c = b, c, 2b + 2c (d = a = b + c) 0, b + c, 2c - b = b, c - b, 2c (d = c - b) These give 0, b + 2c, 3b + c, 4b + 3c = b, c, 4b + 2c, 3b + 3c (d = 2b + c) 0, 2b + c, b + 3c,; 3b + 4c = b, c, 3b + 3c, 2b + 4c (d = b + 2c) 0, 2c - b, 2b + c, b + 3c = b, c - b, 2b + 2c, 3c (d = b + c) 0, b + c, 3c - 2b, 4c - b = b, c - b, 3c, 4c - 2b (d = 2c - b) 0, b + c, 2c - 3b, 3c - 2b = b, 2c, c - 2b, 3c - 3b (d = c - 2b) Now consider the solution 3 0, b + 2c, 3b + c, 4b + 3c = b, c, 4b + 2c, 3b + 3c This will give an ideal solution of degree 4 only i f the same difference occurs between three pairs of terms. The only numerical solutions that satisfy this condition are 14. These give 0, 3, 4, 7 = l , l , 6, 6 0, 5,. 10, 15 = 1, 3, 12, 14 0, 6, • 7, 13 = 1, 3, 10, 12 0, 4, 7, 11 = 1, 2, 9, 10 0, 8, 9, 17 = 2, 3, 14, 15 0, 6, 8, 17, 19 = 1, 3, 12, 14, 20 0, 4, 8, 16, 17 = 1, 2, 10, 14, 18 These give 0, 5, 6, 16, 17, 22 = 1, 2, 10, 12, 20, 21 0, 6, 8, 23, 25, 31 = 1, 3, 11, 20, 28, 30 0, 4, 9, 17, 22, 26 = 1, 2, 12, 14, 24, 25 None of these solutions will generate an ideal solution of degree 6. Theorem 5 follows after considering in a similar manner the remaining four ideal solutions of degree 3. 4. An extension of the problem. In an extension of the Tarry-Escott problem the function M(k) has been defined as the least value of s such that (A) has a solution with k+1 , , k+1 , , k+1 , , ,k+l a, .+ ... + a. f b, + ... + b 1 s 1 s 15. C l e a r l y M(k) ^ N(k) 2: k + 1, while Theorem 3 and Theorem 4 prove that M(k) = N(k) = k + 1 for a l l k ^ 9. Wright [̂ 9, pp.262 proved that M ( k ) ^ N (k 2 ) , and was then \ 10, pp.48 1 able to prove that 4 M(k)<= 7JL_ . 216 The r e s u l t s obtained in Table I a l so apply to M(k) in view of the fo l lowing theorem. . k+1 Theorem 6 M(k) = ^ m i n S 2 p e fi' P ( x ) ( l - x ) ' where Q' i s the c la s s of a l l polynomials whose c o e f f i c i e n t s are in tegers , not a l l zero, and furthermore i f P € fi' then P ( l ) f 0. k+1 Proof For every P £ fi', P ( x ) ( l - x) generates a so lu t i on of (A) of degree k. Assume that th i s s o lu t i on is a l so of degree k+1. Then i t must k+2 be generated by Q(x ) ( l — x) for some Q £ fi. Hence P(x) = (1 - x) Q(x) which i s f a l s e . 16. BIBLIOGRAPHY 1. L. Bas t ien , Sphinx-Oedipe, 8(1913), 171-172. 2. J. Chernick, Ideal so lut ions of the Tar ry -Escot t problem, American Math. Monthly, 44(1937), 626-633. 3. L. E. Dickson, H i s tory of the Theory of Numbers, II, Chelsea Pub l i sh ing Company, New York, 1952. 4. L. E. Dickson, Introduct ion to the Theory of Numbers, The U n i v e r s i t y of Chicago Press, Chicago, 1929. 5. M. F ro lov , B u l l e t i n de l a Societe Mathematique de France, 17(1888-9), 69-83; 20(1892), 69-84. 6. G. H. Hardy and E. M. Wright, An in t roduct ion to the theory of numbers, 4th e d . , Oxford, 1960. 7. Z. A. Melzak, A note on the Tar ry -E sco t t problem, Canadian Math. B u l l . , 4(1961), 233-237. 8. G. Tar ry , L 1 I n termed ia i re des Mathematiciens, 19(1912), 219-221. 9. E. M. Wright, On T a r r y ' s Problem ( I ) , Quart. J. of Math. (Oxford), 6(1935), 261-267. 10. E. M. Wright, On T a r r y ' s Problem ( I I I ) , Quart. J. of Math. (Oxford), 8(1937), 48-50. 17. APPENDIX I DATA FOR TABLE II (a) 0,3,7,10,.23,35)50,53,56,81,82,93,96,97 X« 1,2,5,16,17,42,45,48,63,75,88,91,95,98. Using d = 3 this generates a solution for k = 11 where s = 18, which for d = 4 generates a solution for k = 12 where s = 24. (b) We could not produce solutions for k = 13 and k = 14 where s -= 30 and hence used 0,5,7,19,21,21,25,32,46,47,48,50,53,74,75,78,79,100,103,105,106, 107,121,128,132,132,134,146,148,153. 15 1,2,13,15,15,27;29,30,40,44,51,55,56,65,76,77,88,97,98,102,109, 113,123,124,126,138,138,140,151,152. Using d =. 25 this generates a solution for k = 16 where s = 38 which for d = 27 generates a solution for k = 17 where s = 48 which for d = 21 generates a solution for k = 18 where s = 58 which for d = 31 generates a solution for k = 19 where s = 58 which for d = 29 generates a solution for k = 20 where s = 65. (c). 1,6,8,9,20,23,32,43,44,45,49,57,60,66,68,69,79,80,84,92,101,102, 103,104,105,115,116,119,127,129,131,138,139,140,, 143,143,151,154, 155,163,166,174,175,178,186,186,189,190,191,198,200,202,210,213, 214,224,225,226,227,228,237,245,249,250,260,261,263,269,272,280, 284,285,286,297,306,309,320,321,323,328. 21 2,3,10, lly16, 24,38,39,39,50,51,53,59,63,74,75,76,77,85,89,98,99, 100, 111, 112,113,120,122,124,125,132,133,134,136,144,148,156,159, 160,161,168,169,170,173,181,185,193,195,196,197,204,205,207,209, 216,217,218,229,230,231,240,244,252,253,254,255,266,270,276,278, 279,290,290,291,305,313,318,319,326,327. Using d = 35 this generates a solution for k = 22 where s = 84. 18. APPENDIX II GENERATING SOLUTIONS BY COMPUTER FIGURE 3 READ ISUM, JSUM, LENGTH, NDEGRE, MAXLTH V SUBROUTINE MAXDIF 1 SUBROUTINE NEWSOL ( PRINT LENGTH,. NDEGRE, ISET, JSET no LENGTH - number of terms on one s ide of a s o lu t i on NDEGRE - degree of the so lu t i on ISET - one s ide of a s o l u t i on JSET - remaining side of the so lu t i on MAXLTH - maximum number of terms acceptable on one s ide of a so lu t i on MAXDIF - most frequent d i f f e rence between pa i r s of terms from the same s ide of a so lu t i on 19. Figure 3 is a simple block diagram of the program used to generate solutions of (A) by Theorem 2 starting from any particular solution. Subroutine MAXDIF determined the most frequent difference occuring between pairs of terms from the same side of a given solution. The program was routine but care has to be taken to ensure that for a solution such as 2 0, 3, 3 = 1, I, 4 the difference 3 occurs effectively twice and not four times. One cannot program a computer to simply strike out terms that occur on both sides of a solution of (A), but subroutine NEWSOL generated solutions by Theorem 2 and disposed of common terms by use of an algebraic technique. The following example should indicate the method. 2 The solution 0, 3, 3 = 1, 1, 4 is converted to the generating function „ , 1 - 2x + 2x - x Using Theorem 2 with MAXDIF = 3 is equivalent to multiplying this 3 generating function by 1 - x . Hence 3 4 1 - 2x + 2x - x . 1 - x 3 3 4 1 - 2x + 2x - x x 3 + 2x4 - 2x6 + x 7 1 - 2x + x 3 + x 4 - 2x6 + x 7 which generates the solution 0,. 3, 4, 7 3 1, 1, 6, 6 Subroutine NEWSOL appeared to be most efficient and we present it below. 20. SUBROUTINE NEWSOL (ISET, JSET, LENGTH, MAXDIF, NDEGRE) DIMENSION NP(1500), IX(1500), ISET(200), JSET(200) IE(ISET(LENGTH)-JSET(LENGTH)) 30,30,31 30 NBIG=JSET(LENGTH)+1 NBIG2=2--NBIG GO TO 22 31 ' NBIG=ISET(LENGTH)+1 •NBIG2=2*NBIG 22 DO 20 MX=1,NBIG2 20 NP(MX)=0 DO 21 'JIT=1, LENGTH ISET1=ISET(JIT)+1 JSET1=JSET(JIT)+1 NP(ISET1)=NP(ISET1)+1 21 NP(JSET1)=NP(JSET1)-1 M2=0 DO 41 NAT=1,MAXDIF 41 IX(NAT)=0 LOW=MAXDIF+l NHIGH=NBIG+MAXDIF DO 79 K3=LOW,NHIGH K4=K3-MAXDIF 79 IX(K3)=NP(K4) DO 42 NIS=1,NHIGH NP(NIS)=NP(NIS)-IX(NIS) NPNIS=NP(NIS) M1=ABSF(NPNIS)+M2 42 M2=M1 18=0 19=0 J8=0 J9=0 DO 43 1X1=1,NHIGH IF(NP(IX1)) 44,43,45 44 NP1=-NP(IX1) 18=19+1 I9=I9+NP1 DO 54 L1=I8,I9 MT=IX1-1 54 JSET(L1)=MT GO TO 43 45 NP2=NP(IX1) . J8=J9+1 J9=J9+NP2 DO 55 L2=J8, J9 MP=IX1-1 55 ISET(L2)=MP 43 CONTINUE LENGTH=I9 NDEGRE=NDEGRE+1 RETURN END
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 3 | 8 |
City | Views | Downloads |
---|---|---|
Beijing | 3 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Share to: