Prev: on course! for deriving speed of light from pure math Chapt 19 #205; ATOM TOTALITY
Next: Global Industry - Online Webshop
From: achille on 29 Jun 2010 10:45
On Jun 29, 8:00 pm, David Bernier <david...(a)videotron.ca> wrote:
> 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

The algorithm is pretty simple. Start with an empty set S
(represent elements in a non-averaging subset one going
to construct) and a set of potential candidates A.

1) Let k be the smallest element of A. remove k from A,
2) For every element s of S, test whether 2k-s is in A,
if yes, remove 2k-s from A.
3) put k into A
4) repeat step (1) unless A is empty.

BTW, it seems the longest known non-averaging subset of
1..99 is the following 26 element set.

1 2 4 5 10 11 22 23 25 26 31 32 55 56 64 65 67 68 76 77 82 83 91 92 94
95

It should be useful as a benchmark for your search algorithm.

REF: http://www.research.att.com/~njas/sequences/A065825


From: achille on 29 Jun 2010 11:40
On Jun 29, 10:45 pm, achille <achille_...(a)yahoo.com.hk> wrote:
> 3) put k into A

Sorry, step 3) should be put k into S.

> 4) repeat step (1) unless A is empty.
From: Frederick Williams on 29 Jun 2010 12:07
David Bernier 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 don't know perl,

You lucky fellow.

May I ask if you are just seeking these subsets for fun?

--
I can't go on, I'll go on.
From: master1729 on 29 Jun 2010 11:26
david bernier 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.
>
> thanks,
>
> David Bernier

let t(n) be the smallest number so that n-element nonaveraging set can be selected from 1,2,...,t(n).

then t(n) =< n^(3/2) + 1.

i guess that was in part what you were looking for ?

for infinite sequences we have the formula's :

http://www.research.att.com/~njas/sequences/A003278

http://www.research.att.com/~njas/sequences/A033156

http://www.research.att.com/~njas/sequences/A033157

http://www.research.att.com/~njas/sequences/A004793

http://www.research.att.com/~njas/sequences/A007814

regards

tommy1729
From: David Bernier on 29 Jun 2010 20:12
Frederick Williams wrote:
> David Bernier 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 don't know perl,
>
> You lucky fellow.
>
> May I ask if you are just seeking these subsets for fun?
>

Sure. The answer is: mostly yes. I know about the Green-Tao Theorem
on primes in arithmetic progressions, and also a famous conjecture
of Erdos: if the {a_k}_{1 <=k < oo} are a strictly increasing
sequence of positive integers, and the series
sum_{1<= k < oo} ( 1/a_k) diverges, then the sequence of the
a_k's has non-trivial arithmetic progressions of arbitrary length.

I'm interested, for a given small K, in maximal cardinality
subsets of {1, 2, ... K} that have no non-trivial arithmetic
progressions. I'd like to find a number of maximal subsets
for quite small K ( say from about K = 50 up to possibly 100 or so, if
that's possible without taking too much time). There are some questions
I'd like to study empirically. For example, is the average gap between
consecutive terms larger than average for the terms near K/2 ?

I've been having a look at a paper by William Gasarch, James Glenn and
Clyde P. Kruskal: "Finding Large 3-free Sets I: The Small n Case";
"3-free" means "free of arithmetic progressions of length >= 3".

They find (prove) values of sz(n) for 1<= n <= 187.

Their definition is:
sz(n) is the maximum size of a 3-free subset of {1, 2, 3, ... n};
sz stands for Szemeredi [ their Definition 4].

For example, sz(99) = 26, but also sz(94) = 25 while sz(95) = 26, according
to their Table I.

I don't have the expectation of finding novel results; I can't see
how it might help with research I do for work.

It's fun to do one's own explorations. It's not so fun when I try
to program improved methods and there all still bugs in the program.

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