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 27 Jun 2010 06:49 According to the output of a program I wrote, the following sequence of 19 numbers from 1 to 99 should contain no arithmetic progression(s) of length three or more: 5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99. As I'm testing the program, I'd be glad to know if there's an error. thanks, David Bernier
From: David C. Ullrich on 27 Jun 2010 07:45 On Sun, 27 Jun 2010 06:49:09 -0400, David Bernier <david250(a)videotron.ca> wrote: >According to the output of a program I wrote, >the following sequence of 19 numbers from 1 to 99 >should contain no arithmetic progression(s) of >length three or more: > >5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99. > >As I'm testing the program, I'd be glad to know if there's >an error. If the question is just whether that sequence indeed contains no non-trivial arithmetic progressions, that's easy enough to check; the sequence is short enough that utterly stupid brute-force code works just fine. No, it doesn't: s=[5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99] for j in range(len(s)): for k in range(j+1,len(s)): for n in range(k+1, len(s)): if 2*s[k]==s[j]+s[n]: print 'oops', s[j],s[k],s[n] print 'done' >thanks, > >David Bernier
From: David Bernier on 27 Jun 2010 12:41 David C. Ullrich wrote: > On Sun, 27 Jun 2010 06:49:09 -0400, David Bernier > <david250(a)videotron.ca> wrote: > >> According to the output of a program I wrote, >> the following sequence of 19 numbers from 1 to 99 >> should contain no arithmetic progression(s) of >> length three or more: >> >> 5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99. >> >> As I'm testing the program, I'd be glad to know if there's >> an error. > > If the question is just whether that sequence indeed contains > no non-trivial arithmetic progressions, that's easy enough to > check; the sequence is short enough that utterly stupid > brute-force code works just fine. No, it doesn't: > > s=[5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, > 99] > > for j in range(len(s)): > for k in range(j+1,len(s)): > for n in range(k+1, len(s)): > if 2*s[k]==s[j]+s[n]: > print 'oops', s[j],s[k],s[n] > print 'done' > [...] Thank you very much. I hadn't used Python scripts before to do something of mathematical interest to me. One feature I like is that no compilation is required, and scripts can be edited easily, for example to try adding an extra number to the 's' in your script. That way, I believe I've found a 21-element non-averaging subset by adding the number 20 to a 20-element set found by my C program; The 21-element subset as an 's' string (or something) is: [1, 6, 7, 9, 14, 20, 24, 30, 32, 35, 37, 49, 70, 71, 75, 77, 82, 85, 86, 96, 98] David Bernier
From: Robert Israel on 27 Jun 2010 16:34 David C. Ullrich <ullrich(a)math.okstate.edu> writes: > On Sun, 27 Jun 2010 06:49:09 -0400, David Bernier > <david250(a)videotron.ca> wrote: > > >According to the output of a program I wrote, > >the following sequence of 19 numbers from 1 to 99 > >should contain no arithmetic progression(s) of > >length three or more: > > > >5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99. > > > >As I'm testing the program, I'd be glad to know if there's > >an error. > > If the question is just whether that sequence indeed contains > no non-trivial arithmetic progressions, that's easy enough to > check; the sequence is short enough that utterly stupid > brute-force code works just fine. No, it doesn't: That is: "No, it doesn't contain any non-trivial arithmetic progressions", rather than "No, it's not true that the sequence contains no non-trivial arithmetic progressions", which was how I initially interpreted your "No, it doesn't". > s=[5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, > 99] > > for j in range(len(s)): > for k in range(j+1,len(s)): > for n in range(k+1, len(s)): > if 2*s[k]==s[j]+s[n]: > print 'oops', s[j],s[k],s[n] > print 'done' Slightly less brute force is the following Maple (13 and up) code: s:= {5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99}; (2 *~ s) intersect {seq(op(a +~ (s minus {a})), a=s)}; The result being {} means that there are no non-trivial arithmetic progressions in s. Also of interest: now that we know s has no non-trivial arithmetic progressions, here are all x <= 200 such that s union {x} has none. {$1 .. 200} minus (s union {seq(op((1/2) *~ (a +~ (s minus {a}))),a=s)} union {seq(op(2*a -~ (s minus {a})), a = s)}); {77, 109, 113, 115, 125, 129, 135, 138, 141, 145, 149, 150, 152, 154, 157, 160, 163, 166, 169, 171, 172, 183, 186, 187, 188, 191, 194, 195, 196, 197, 198, 199, 200} -- Robert Israel israel(a)math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
From: David Bernier on 28 Jun 2010 02:49
Robert Israel wrote: > David C. Ullrich<ullrich(a)math.okstate.edu> writes: > >> On Sun, 27 Jun 2010 06:49:09 -0400, David Bernier >> <david250(a)videotron.ca> wrote: >> >>> According to the output of a program I wrote, >>> the following sequence of 19 numbers from 1 to 99 >>> should contain no arithmetic progression(s) of >>> length three or more: >>> >>> 5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, 99. >>> >>> As I'm testing the program, I'd be glad to know if there's >>> an error. >> >> If the question is just whether that sequence indeed contains >> no non-trivial arithmetic progressions, that's easy enough to >> check; the sequence is short enough that utterly stupid >> brute-force code works just fine. No, it doesn't: > > That is: "No, it doesn't contain any non-trivial arithmetic progressions", > rather than "No, it's not true that the sequence contains no non-trivial > arithmetic progressions", which was how I initially interpreted your "No, it > doesn't". > > >> s=[5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, >> 99] >> >> for j in range(len(s)): >> for k in range(j+1,len(s)): >> for n in range(k+1, len(s)): >> if 2*s[k]==s[j]+s[n]: >> print 'oops', s[j],s[k],s[n] >> print 'done' > > Slightly less brute force is the following Maple (13 and up) code: > > s:= {5, 6, 8, 9, 16, 22, 25, 31, 47, 58, 64, 68, 74, 76, 82, 92, 93, 95, > 99}; > (2 *~ s) intersect {seq(op(a +~ (s minus {a})), a=s)}; > > The result being {} means that there are no non-trivial arithmetic > progressions in s. > > Also of interest: now that we know s has no non-trivial arithmetic > progressions, here are all x<= 200 such that s union {x} has none. > > {$1 .. 200} minus (s union {seq(op((1/2) *~ (a +~ (s minus {a}))),a=s)} union > {seq(op(2*a -~ (s minus {a})), a = s)}); > > {77, 109, 113, 115, 125, 129, 135, 138, 141, 145, 149, 150, 152, 154, 157, > 160, 163, 166, 169, 171, 172, 183, 186, 187, 188, 191, 194, 195, 196, 197, > 198, 199, 200} I'm still asking my program in C to find 20-element subsets of {1, 2, ... 99} which contain no non-trivial arithmetic progressions. I've found one or two 21-element subsets working manually with Python scripts obtained by editing David Ullrich's script. So far, I've found no 22-element subsets. The raw data below is in unordered sequences. I've also uploaded the file to here: < http://berniermath.net/nonaveraging.txt > . David Bernier ---------- unordered raw data ------------------------------------- [david(a)localhost Branch_arith_series_avoid]$ ./sequine_n20a.out 37, 77, 1, 30, 32, 98, 86, 7, 70, 49, 96, 82, 14, 6, 35, 75, 24, 85, 9, 71, ok? ========================================================================= [david(a)localhost Branch_arith_series_avoid]$ ./sequine_n20c.out 9, 37, 94, 16, 43, 95, 74, 20, 82, 5, 60, 17, 89, 36, 76, 19, 80, 62, 97, 8, =========================================================================== s=[1, 3, 13, 15, 26, 30, 31, 40, 42, 46, 60, 64, 70, 72, 73, 85, 87, 92, 93, 95, 96] N = 21 ... =========================================================================== [david(a)localhost Branch_arith_series_avoid]$ ./sequine_n20b.out 29, 70, 90, 15, 6, 3, 4, 74, 97, 23, 99, 33, 10, 11, 96, 92, 30, 59, 71, 34, ok? ============================================================================ [david(a)localhost Branch_arith_series_avoid]$ ./sequine_n20b.out 77, 84, 67, 16, 53, 59, 99, 8, 82, 61, 66, 4, 25, 96, 85, 3, 54, 11, 27, 30, ok? ============================================================================ [david(a)localhost Branch_arith_series_avoid]$ ./sequine_n20b.out 78, 2, 90, 93, 11, 72, 5, 97, 24, 28, 74, 86, 12, 68, 69, 31, 61, 9, 30, 99, ============================================================================= |