non-averaging subsets of {1, 2, 3, ... 99} [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 2 Jul 2010 02:16

achille wrote:
> On Jun 29, 8:00 pm, David Bernier<david...(a)videotron.ca> wrote:
>> achille wrote:
[...]

[achille:]
>>> 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" );

[David Bernier:]
>> 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 reply from achille below:]

> 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
[ was corrected by achille to "put k into S" soon after ...]

> 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

I see your algorithm as close to a "depth first" method.
The problem is successively solved for 1, 2, 3, ... 24
element subsets of {1, 2 ... 99}.

Because of your:
(2) For every element s of S, test whether 2k-s is in A,
if yes, remove 2k-s from A.

it seems at each step up in length, the number added is the
smallest candidate (from A) which, added to the current
set of selected numbers S, produces a set
which is still non-averaging [I should check
for myself that (1), (2) and (3) implies
the set with one element added is non-averaging].

There's a method in the paper by Gasarch and others called
backtracking (going back by removing elements of S
and starting with a new "candidate" at an earlier stage).
The full back-tracking method seems a bit complicated
to implement for me.

So I think I see better: you remove
k (possibly temporarily?) from the candidates because
if k is eventually added to S,
(2k-s) + s = 2k implies that (2k-s) can't be in S
if k and s are in S. My question is:
if 'k' isn't added to S, do you cancel the eliminations
of the 2k-s from A that were done in step (2)?

Anyway, I'm looking into simple kinds of depth first
(such as first creating a non-averaging set of
13 to 20 numbers) [the "fixed" numbers]
combined with testing many choices of candidates.
I was able to get a 25-element set but no
26-element sets so far.

Thanks for your explanations,

David Bernier

From: achille on 2 Jul 2010 02:54

On Jul 2, 2:16 pm, David Bernier <david...(a)videotron.ca> wrote:
> achille wrote:
> > On Jun 29, 8:00 pm, David Bernier<david...(a)videotron.ca> wrote:
> >> achille wrote:
>
> [...]
>
> [achille:]
>
> >>> 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" );
>
> [David Bernier:]
>
>
>
> >> 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 reply from achille below:]
>
> > 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
>
> [ was corrected by achille to "put k into S" soon after ...]
>
> > 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
>
> I see your algorithm as close to a "depth first" method.
> The problem is successively solved for 1, 2, 3, ... 24
> element subsets of {1, 2 ... 99}.
>
> Because of your:
> (2) For every element s of S, test whether 2k-s is in A,
> if yes, remove 2k-s from A.
>
> it seems at each step up in length, the number added is the
> smallest candidate (from A) which, added to the current
> set of selected numbers S, produces a set
> which is still non-averaging [I should check
> for myself that (1), (2) and (3) implies
> the set with one element added is non-averaging].
>
> There's a method in the paper by Gasarch and others called
> backtracking (going back by removing elements of S
> and starting with a new "candidate" at an earlier stage).
> The full back-tracking method seems a bit complicated
> to implement for me.
>
> So I think I see better: you remove
> k (possibly temporarily?) from the candidates because
> if k is eventually added to S,
> (2k-s) + s = 2k implies that (2k-s) can't be in S
> if k and s are in S. My question is:
> if 'k' isn't added to S, do you cancel the eliminations
> of the 2k-s from A that were done in step (2)?
>
> Anyway, I'm looking into simple kinds of depth first
> (such as first creating a non-averaging set of
> 13 to 20 numbers) [the "fixed" numbers]
> combined with testing many choices of candidates.
> I was able to get a 25-element set but no
> 26-element sets so far.
>
> Thanks for your explanations,
>
> David Bernier

The basic idea of the algorithm I used is to build
the non-averaging set by adding the elements from
smallest to biggest. Whenever the algorithm reaches
step 1, any element of A can be added to S to create
a new non-averaging set. I just pick k to be the
smallest one. In fact, you can modify step 1 to:

1)' let k be any element from A, remove all
elements <= k from A.

the algorithm still works.

About step 2), it is easy to check for any remaining
elements s > k on A, the only way that

S U {k} U {s} is NOT non-averaging

is when k = (s+x)/2 for some element x in S. So after
step 2), every element of A can be added to S U {k} to
create a new non-averaging set.

Hope this clarifies the matter.

From: David Bernier on 2 Jul 2010 10:23

From: David Bernier on 4 Jul 2010 01:26

From: David Bernier on 12 Jul 2010 12:15

achille wrote:
> On Jul 2, 2:16 pm, David Bernier<david...(a)videotron.ca> wrote:
>> achille wrote:
>>> On Jun 29, 8:00 pm, David Bernier<david...(a)videotron.ca> wrote:
>>>> achille wrote:
>>
>> [...]
>>
>> [achille:]
>>
>>>>> 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" );
>>
>> [David Bernier:]
>>
>>
>>
>>>> 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 reply from achille below:]
>>
>>> 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
>>
>> [ was corrected by achille to "put k into S" soon after ...]
>>
>>> 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
>>
>> I see your algorithm as close to a "depth first" method.
>> The problem is successively solved for 1, 2, 3, ... 24
>> element subsets of {1, 2 ... 99}.
>>
>> Because of your:
>> (2) For every element s of S, test whether 2k-s is in A,
>> if yes, remove 2k-s from A.
>>
>> it seems at each step up in length, the number added is the
>> smallest candidate (from A) which, added to the current
>> set of selected numbers S, produces a set
>> which is still non-averaging [I should check
>> for myself that (1), (2) and (3) implies
>> the set with one element added is non-averaging].
>>
>> There's a method in the paper by Gasarch and others called
>> backtracking (going back by removing elements of S
>> and starting with a new "candidate" at an earlier stage).
>> The full back-tracking method seems a bit complicated
>> to implement for me.
>>
>> So I think I see better: you remove
>> k (possibly temporarily?) from the candidates because
>> if k is eventually added to S,
>> (2k-s) + s = 2k implies that (2k-s) can't be in S
>> if k and s are in S. My question is:
>> if 'k' isn't added to S, do you cancel the eliminations
>> of the 2k-s from A that were done in step (2)?

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:

adjusting empirically from 27 numbers to 41 numbers, I got:

[david(a)localhost achille_method_B]$ ./twuskips_hui443w2.out

found 41 numbers
minaccept = 44
1,1,0,1,0,2,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
2,4,5,9,10,19,20,24,25,27,32,42,47,51,53,56,58,66,68,71,72,121,136,141,143,144,148,149,156,158,166,178,179,181,182,187,194,197,199,203,205,

ok?
======

The initial '1' in [1,1,0,1,0,2,0,2] tells us to skip the smallest candidate for
the first selection, which is '1'.

It passes David Ullrich's Python script:

[david(a)localhost Some_Python]$ ./dcu_check_july12_f41.py
done
[david(a)localhost Some_Python]$ cat dcu_check_july12_f41.py
#! /usr/bin/env python

s=[2,4,5,9,10,19,20,24,25,27,32,42,47,51,53,56,58,66,68,71,72,121,136,141,143,144,148,149,156,158,166,178,179,181,182,187,194,197,199,203,205]

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'

There are indeed 41 numbers, and the first is '2'.

So S={1,3,4, .............. 198,202,204} is also 3-free
(subtracting 1 from every number in the vector 's' in the Python script).

----

Gasarch, Glenn and Kruskal in
"Finding large 3-free sets I: The small n case",
Reference:
<
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4NYD8X3-2&_user=10&_coverDate=06%2F30%2F2008&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=47506f553e3d10afcf7914401969de11
>

or as a preprint #7 here:
< http://www.cs.umd.edu/~gasarch/papers/papers.html >

in their Table 3 (page 35) give
sz(194) >= 41 and
sz(193) >= 40.

Also, they give sz(204) >= 42.

----

The C program I wrote together with the Python script give
sz(204) >= 41. vs. sz(194) >= 41 (Gasarch, Glenn and Kruskal; obviously
they have a better bound.

Anyway, at the moment I'm trying to optimize the probability of skipping
"potential candidates".

--------------------------------------------------
/*** The higher minaccept is, the greater the probability of
skipping over a potential candidate.
G8 is a macro returning as a signed 16-bit int
a number from 0 to 255 inclusive ***/

#include <stdio.h>
#include <math.h>
#define Nmersenne 624
#define Mmersenne 397
#define MATRIX_A 0x9908b0dfUL
#define UPPER_MASK 0x80000000UL
#define LOWER_MASK 0x7fffffffUL
#define G8 genrand_int8()
#define MIN_ACCEPT 40
#define RANGE 210
static unsigned long mt[Nmersenne];
static int mti=Nmersenne+1;
void init_genrand(unsigned long s)
{
mt[0]= s & 0xffffffffUL;
for (mti=1; mti<Nmersenne; mti++) {
mt[mti] =
(1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
mt[mti] &= 0xffffffffUL;
}
}
void init_by_array(unsigned long[], int);
void init_by_array(unsigned long init_key[], int key_length)
{
int i, j, k;
init_genrand(19650218UL);
i=1; j=0;
k = (Nmersenne>key_length ? Nmersenne : key_length);
for (; k; k--) {
mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
+ init_key[j] + j;
mt[i] &= 0xffffffffUL;
i++; j++;
if (i>=Nmersenne) { mt[0] = mt[Nmersenne-1]; i=1; }
if (j>=key_length) j=0;
}
for (k=Nmersenne-1; k; k--) {
mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
- i;
mt[i] &= 0xffffffffUL;
i++;
if (i>=Nmersenne) { mt[0] = mt[Nmersenne-1]; i=1; }
}
mt[0] = 0x80000000UL;
}
int genrand_int8(void)
{
unsigned long y;
static unsigned long mag01[2]={0x0UL, MATRIX_A};
if (mti >= Nmersenne) {
int kk;
if (mti == Nmersenne+1)
init_genrand(5489UL);
for (kk=0;kk<Nmersenne-Mmersenne;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+Mmersenne] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
for (;kk<Nmersenne-1;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+(Mmersenne-Nmersenne)] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
y = (mt[Nmersenne-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[Nmersenne-1] = mt[Mmersenne-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
mti = 0;
}
y = mt[mti++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return ((int) (y>>24));
}

int main(void)
{
int selection[RANGE];
int candidate[RANGE];
int i;
int j;
int k;
int m;
int s;
int delete;
int answer;
int nfound;
int has_candidates;
int candidate_found;
int accept;
int minaccept;
int skips[RANGE];
int number_to_do;
unsigned long initmersenne[5]={0x65b,0x967,0xe897e,0xccc,0x123};
int lengthmersenne=5;

number_to_do = 41;

init_by_array(initmersenne,lengthmersenne);

while( 1 == 1)
{

nfound = 0;
for(i=0; i<RANGE; i++)
{
selection[i] = 0;
candidate[i] = 1;
skips[i] = 0;
}

has_candidates = 1;

while(has_candidates == 1)
{
// find smallest candidate
candidate_found = 0;
k=0;

while(candidate_found == 0)
{

minaccept = 53 ;
if(nfound>20)
{
minaccept = 44;
}

accept = 1;
if( (G8) < minaccept)
{
accept = 0;

}

if((candidate[k] == 1) && (accept == 0))
{
skips[nfound]++;
candidate[k] = 0;
}

if((candidate[k] == 1) && (accept == 1))
{
candidate_found = 1;
}

if(candidate_found == 0)
{
k++;
}

}

candidate[k] = 0;
for(s=0;s<RANGE;s++)
{
if(selection[s] == 1)
{
delete = k + k - s;
if( (0<= delete) && (delete <= RANGE) )
{
candidate[delete] = 0;
}
}
}
selection[k] = 1;
nfound++;

j=0;
for(i=0; i<RANGE;i++)
{
j = j + candidate[i];
}
if(j == 0)
{
has_candidates = 0;
}
else
{
has_candidates = 1;
}

if( (j+nfound)<number_to_do)
{
break;
}
}

if( nfound >= 40)
{
printf("\n\n found %d numbers\n", nfound);
printf("minaccept = %d\n", minaccept);
for(m=0; m< nfound; m++)
{
printf("%d,", skips[m]);
}

printf("\n");

for(m=0;m<RANGE;m++)
{
if(selection[m] == 1)
{
printf("%d,", m+1);
}
}

printf("\n");

printf("\nok?\n");
//scanf("%d", &answer);

fflush(stdout);
}
} // while 1 == 1

printf("\n\n");
return 0;
}
----------------------------------------------------

David Bernier

>>
>> Anyway, I'm looking into simple kinds of depth first
>> (such as first creating a non-averaging set of
>> 13 to 20 numbers) [the "fixed" numbers]
>> combined with testing many choices of candidates.
>> I was able to get a 25-element set but no
>> 26-element sets so far.
>>
>> Thanks for your explanations,
>>
>> David Bernier
>
> The basic idea of the algorithm I used is to build
> the non-averaging set by adding the elements from
> smallest to biggest. Whenever the algorithm reaches
> step 1, any element of A can be added to S to create
> a new non-averaging set. I just pick k to be the
> smallest one. In fact, you can modify step 1 to:
>
> 1)' let k be any element from A, remove all
> elements<= k from A.
>
> the algorithm still works.
>
> About step 2), it is easy to check for any remaining
> elements s> k on A, the only way that
>
> S U {k} U {s} is NOT non-averaging
>
> is when k = (s+x)/2 for some element x in S. So after
> step 2), every element of A can be added to S U {k} to
> create a new non-averaging set.
>
> Hope this clarifies the matter.
>
>
>
>
>
>
>
>
>

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