Prev: on course! for deriving speed of light from pure math Chapt 19 #205; ATOM TOTALITY
Next: Global Industry - Online Webshop
From: achille on 28 Jun 2010 04:52
On Jun 28, 2:49 pm, David Bernier <david...(a)videotron.ca> wrote:
> Robert Israel wrote:
> > David C. Ullrich<ullr...(a)math.okstate.edu>  writes:
>
> >> On Sun, 27 Jun 2010 06:49:09 -0400, David Bernier
> >> <david...(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,
> =============================================================================

A 24-element non-average subset generated by perl script at end:

1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83,
85, 86, 91, 92, 94, 95

my @A = (1..99);
my %S = ();
while(defined(my $k = shift(@A) ) ){
@A = grep { !defined( $S{2*$k - $_} ) } @A;
$S{$k} = 1;
}
print( join( ", ", sort { $a <=> $b } keys %S ), "\n" );
From: Richard Tobin on 28 Jun 2010 11:10
In article <rbisrael.20100627180804$6697(a)news.acm.uiuc.edu>,
Robert Israel <israel(a)math.MyUniversitysInitials.ca> wrote:

>> 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".

I initially interpreted it as "No, it turns out that brute force
doesn't work just fine".

-- Richard
From: David C. Ullrich on 28 Jun 2010 16:39
On Sun, 27 Jun 2010 15:34:19 -0500, Robert Israel
<israel(a)math.MyUniversitysInitials.ca> 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".

Not untrue, thanks.

>
>> 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}

From: David C. Ullrich on 28 Jun 2010 16:48
On Sun, 27 Jun 2010 12:41:43 -0400, David Bernier
<david250(a)videotron.ca> wrote:

>[...]
>
>Thank you very much. I hadn't used Python scripts before to do
>something of mathematical interest to me.

One tiny hint about Python versus math:

x = [1,2]

print x+x # prints [1,2,1,2]

class Vector:

def __init__(self, data):
self.data = data

def __getitem__(self, j):
return self.data[j]

def __add__(self, other):
"""There are much `better' ways to write this
method; what's below is just meant to be easy to
follow if you know no Python"""

data = []
for j in range(len(self.data)):
data.append(self[j] + other[j])
return Vector(data)

def __str__(self):
return str(self.data)

x = Vector([1,2])

print x+x

>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: David Bernier on 29 Jun 2010 08:00
achille wrote:
> On Jun 28, 2:49 pm, David Bernier<david...(a)videotron.ca> wrote:
[...]

>> 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> .

[...]

> A 24-element non-average subset generated by perl script at end:
>
> 1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83,
> 85, 86, 91, 92, 94, 95
>
> my @A = (1..99);
> my %S = ();
> while(defined(my $k = shift(@A) ) ){
> @A = grep { !defined( $S{2*$k - $_} ) } @A;
> $S{$k} = 1;
> }
> print( join( ", ", sort { $a<=> $b } keys %S ), "\n" );

That's impressive. I don't know perl, so I
don't understand the algorithm.

I'm now trying shorter ranges than 1 to 99.
For 1 to 49 inclusive, there's a sequence of
16 numbers with no non-trivial arithmetic
progressions:

[2, 4, 5, 7, 13, 14, 16, 20, 29, 32, 34, 40, 41, 43, 47, 49].

For a sequence of 17 numbers, the shortest range I've found
so far that works is 1 to 59:

[1, 3, 4, 8, 9, 16, 19, 20, 25, 33, 38, 44, 45, 48, 53, 54, 59].

David Bernier
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: on course! for deriving speed of light from pure math Chapt 19 #205; ATOM TOTALITY
Next: Global Industry - Online Webshop