non-averaging subsets of {1, 2, 3, ... 99}
in [Math]
|
Prev: on course! for deriving speed of light from pure math Chapt 19 #205; ATOM TOTALITY
Next: Global Industry - Online Webshop
From: David Bernier on 22 Jul 2010 10:41 David Bernier wrote: [...] > I think I've done some more understanding. In achille's method, > the algorithm is committed to keeping the least candidate (i.e. k) > after a 3-free set with with 3 (viz. 4, 5, 6 ... 20 integers has been > found). > > Isn't this a "greedy algorithm"? > > Searching Google Books with > Richard K. Guy Odlyzko Stanley greedy algorithm > > one arrives at R. K. Guy (2004) page 319, > at: > "Odlyzko & Stanley construct the sequence S(m) > of positive integers with a_0 = 0, > a_1 = m, and each subsequent a_{n+1} is the least > number [strictly] greater than a_n so that > {a_0, a_1, ... a_{n+1} } does not contain a > non-trivial arithmetic progression of length >=3." > { R. K. Guy, "Unsolved problems in number theory", 2004}. > > Richard Guy gives the example > S(1) = 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, > 82, 84, 85, 90, 91, 93, 94 ... 24 terms. > > Now if we add one to each number in S(1) we get: > (S(1) +1) > 1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, > 85, 86, 91, 92, 94, 95 .... [up to 24 terms]. > > I get that the 24-term sequence immediately above is the same as > the one given by achille at the end of his post in this thread of > 28 June, '10: > < http://mathforum.org/kb/message.jspa?messageID=7109763 > . > > So achille's method produces a finite sequence related to > S(1) of Odlyzko & Stanley. I think I now understand the > algorithm of achille and it seems quite or very efficient. > > I borrowed from Odlyzko & Stanley in skipping zero "potential candidates" > or more. This can happen before the first selected number, the second, etc. > > I'm now exploring in a randomized way (Odlyzko & Stanley)/achille > with various probabilities of skipping "potential candidates" in C: [...] For sets of 42 numbers that are non-averaging, it's taken about two days to go down to range: 1-208 from range: 1-209. S = {1,3,4,8,9,11,16,20,22,25,27,48,52,54,55,57,63,64,68,70,75, 91,126,140,143,144,150,152,158,159,163,165,169,170,185,191,193,199,202,203,206,208} S should be a 42-number non-averaging subset of {1,2,3, ... 208}. Above 209, limiting skipped candidates to seven was time-saving. The set with a 1-209 range skips 10 candidates. If we always accept the candidate for 1st number and 42nd number, there are choices #1 to #40 where one could skip a candidate. C(40, 10) = 847,660,528 which is quite a lot. A 42-element subset of {1,2,.... 204} is given in Gasarch, Glenn and Kruskal [2008]. David Bernier --------------- program output ---------------------- range = 208, found 42 numbers 0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0, // above are th skips as 1's. After selecting 1 to be in S, 2 is a candidate // to be in S. The second number above being a '1' indicates to jump over // one candidate [i.e. the number 2] and add the very next candidate to // S; then S = {1, 3, ... } S = {1,3,4,8,9,11,16,20,22,25,27,48,52,54,55,57,63,64,68,70,75, 91,126,140,143,144,150,152,158,159,163,165,169,170,185,191,193,199,202,203,206,208} |