Skip to main content
Post Undeleted by Oleg567
added 131 characters in body
Source Link
Oleg567
  • 131
  • 4

I get $\large\bf 18$$18$ sum-free binary vectors recently.

(UPDATE: It is not top-result now. Brendan McKay obtained $\large\bf 19$ sum-free binary vectors. See his answer, update Feb 24.)

A few examples of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$;

$\qquad(1,0,0,0,1,1,1,1,0,1)$,
$\qquad(0,1,0,1,0,0,1,0,1,0)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,0,1,1,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,1,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,0,1,0,1,1,0,1,0,0)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$.


(Here is discussion of sum testing - as wide comment for Brendan McKay)

Testing of all sums is slow, when you'll generate all sums, and compare each-other. If there are $n$ vectors, then there are $N=2^n$ sums. Naive comparison will take $O(N^2)=O(2^{2n})$ of time.

Good way to construct all sums:

shown on an example of $5$ vectors $a,b,c,d,e$.

There are $2^5=32$ sums.

1-st step: Constructing of sums:

  1. $s[0]=0$;
  2. $s[1]=a$;
  3. $s[2]=b+s[0]$, $s[3]=b+s[1]$;
  4. $s[4]=c+s[0]$, $s[5]=c+s[1]$, $s[6]=c+s[2]$, $s[7]=c+s[3]$;
  5. $s[8+i]=d+s[i]$, where $i=0,1,...,7$;
  6. $s[16+i]=e+s[i]$, where $i=0,1,...,15$.

Time capacity is $O(n\times N) = O(n\times 2^n)$.

2-nd step: Sorting of sums:

Fast sorting methods are quick-sort, heap-sort etc...

Time capacity is $O(N \log N) = O(2^n \times n)$.

3-nd step: Comparison of neighboring sums:

for each $i = 1,..,N-1$ just compare $s[i-1]$ and $s[i]$.

Time capacity is $O(N) = O(2^n)$.

So, total time capacity is $O(n\times N) = O(n\times 2^n)$. Much faster than $O(N^2)$.

I get $\large\bf 18$ sum-free binary vectors recently.

A few examples of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$;

$\qquad(1,0,0,0,1,1,1,1,0,1)$,
$\qquad(0,1,0,1,0,0,1,0,1,0)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,0,1,1,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,1,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,0,1,0,1,1,0,1,0,0)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$.


(Here is discussion of sum testing - as wide comment for Brendan McKay)

Testing of all sums is slow, when you'll generate all sums, and compare each-other. If there are $n$ vectors, then there are $N=2^n$ sums. Naive comparison will take $O(N^2)=O(2^{2n})$ of time.

Good way to construct all sums:

shown on an example of $5$ vectors $a,b,c,d,e$.

There are $2^5=32$ sums.

1-st step: Constructing of sums:

  1. $s[0]=0$;
  2. $s[1]=a$;
  3. $s[2]=b+s[0]$, $s[3]=b+s[1]$;
  4. $s[4]=c+s[0]$, $s[5]=c+s[1]$, $s[6]=c+s[2]$, $s[7]=c+s[3]$;
  5. $s[8+i]=d+s[i]$, where $i=0,1,...,7$;
  6. $s[16+i]=e+s[i]$, where $i=0,1,...,15$.

Time capacity is $O(n\times N) = O(n\times 2^n)$.

2-nd step: Sorting of sums:

Fast sorting methods are quick-sort, heap-sort etc...

Time capacity is $O(N \log N) = O(2^n \times n)$.

3-nd step: Comparison of neighboring sums:

for each $i = 1,..,N-1$ just compare $s[i-1]$ and $s[i]$.

Time capacity is $O(N) = O(2^n)$.

So, total time capacity is $O(n\times N) = O(n\times 2^n)$. Much faster than $O(N^2)$.

I get $18$ sum-free binary vectors recently.

(UPDATE: It is not top-result now. Brendan McKay obtained $\large\bf 19$ sum-free binary vectors. See his answer, update Feb 24.)

A few examples of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$;

$\qquad(1,0,0,0,1,1,1,1,0,1)$,
$\qquad(0,1,0,1,0,0,1,0,1,0)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,0,1,1,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,1,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,0,1,0,1,1,0,1,0,0)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$.


(Here is discussion of sum testing - as wide comment for Brendan McKay)

Testing of all sums is slow, when you'll generate all sums, and compare each-other. If there are $n$ vectors, then there are $N=2^n$ sums. Naive comparison will take $O(N^2)=O(2^{2n})$ of time.

Good way to construct all sums:

shown on an example of $5$ vectors $a,b,c,d,e$.

There are $2^5=32$ sums.

1-st step: Constructing of sums:

  1. $s[0]=0$;
  2. $s[1]=a$;
  3. $s[2]=b+s[0]$, $s[3]=b+s[1]$;
  4. $s[4]=c+s[0]$, $s[5]=c+s[1]$, $s[6]=c+s[2]$, $s[7]=c+s[3]$;
  5. $s[8+i]=d+s[i]$, where $i=0,1,...,7$;
  6. $s[16+i]=e+s[i]$, where $i=0,1,...,15$.

Time capacity is $O(n\times N) = O(n\times 2^n)$.

2-nd step: Sorting of sums:

Fast sorting methods are quick-sort, heap-sort etc...

Time capacity is $O(N \log N) = O(2^n \times n)$.

3-nd step: Comparison of neighboring sums:

for each $i = 1,..,N-1$ just compare $s[i-1]$ and $s[i]$.

Time capacity is $O(N) = O(2^n)$.

So, total time capacity is $O(n\times N) = O(n\times 2^n)$. Much faster than $O(N^2)$.

Post Deleted by Oleg567
Source Link
Oleg567
  • 131
  • 4

I get $\large\bf 18$ sum-free binary vectors recently.

A few examples of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$;

$\qquad(1,0,0,0,1,1,1,1,0,1)$,
$\qquad(0,1,0,1,0,0,1,0,1,0)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,0,1,1,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,1,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,0,1,0,1,1,0,1,0,0)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$.


(Here is discussion of sum testing - as wide comment for Brendan McKay)

Testing of all sums is slow, when you'll generate all sums, and compare each-other. If there are $n$ vectors, then there are $N=2^n$ sums. Naive comparison will take $O(N^2)=O(2^{2n})$ of time.

Good way to construct all sums:

shown on an example of $5$ vectors $a,b,c,d,e$.

There are $2^5=32$ sums.

1-st step: Constructing of sums:

  1. $s[0]=0$;
  2. $s[1]=a$;
  3. $s[2]=b+s[0]$, $s[3]=b+s[1]$;
  4. $s[4]=c+s[0]$, $s[5]=c+s[1]$, $s[6]=c+s[2]$, $s[7]=c+s[3]$;
  5. $s[8+i]=d+s[i]$, where $i=0,1,...,7$;
  6. $s[16+i]=e+s[i]$, where $i=0,1,...,15$.

Time capacity is $O(n\times N) = O(n\times 2^n)$.

2-nd step: Sorting of sums:

Fast sorting methods are quick-sort, heap-sort etc...

Time capacity is $O(N \log N) = O(2^n \times n)$.

3-nd step: Comparison of neighboring sums:

for each $i = 1,..,N-1$ just compare $s[i-1]$ and $s[i]$.

Time capacity is $O(N) = O(2^n)$.

So, total time capacity is $O(n\times N) = O(n\times 2^n)$. Much faster than $O(N^2)$.