Timeline for Number of vectors so that no two subset sums are equal
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2014 at 22:09 | comment | added | Benjamin Dickman | [So your results match up, thus far, with oeis.org/A214051.] | |
| Feb 25, 2014 at 3:47 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 122 characters in body
|
| Feb 24, 2014 at 15:49 | comment | added | Simd | That is great! I have added conjecture which exactly fits the results we have so far. | |
| Feb 24, 2014 at 15:22 | comment | added | Oleg567 | Your set(example) of size $19$ for $n=10$ - it is awesome! very-very nice done! I checked. It works. | |
| Feb 23, 2014 at 23:43 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 1 characters in body
|
| Feb 23, 2014 at 23:02 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 687 characters in body
|
| Feb 23, 2014 at 0:27 | comment | added | Brendan McKay | I also got some of size 16 for $n=9$. | |
| Feb 18, 2014 at 11:32 | comment | added | Brendan McKay | I got some of size 14 for $n=8$. | |
| Feb 18, 2014 at 7:37 | comment | added | Oleg567 | @BrendanMcKay, I described some way to test the condition without enumerating subsets in my answer here. I hope it is fast and convenient. Check it for $n=7$ and compare running time please. But use a fast sorting algo. It is necessary condition of good speed. | |
| Feb 18, 2014 at 6:54 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 159 characters in body
|
| Feb 18, 2014 at 2:14 | history | edited | Brendan McKay | CC BY-SA 3.0 |
add more data
|
| Feb 17, 2014 at 7:15 | comment | added | marshall | Testing if a given set of vectors is a solution is NP-hard I believe. This doesn't of course tell you much about how hard it will be in practice and it tells you nothing about how hard it is to solve the problem we actually want to solve (i.e. what is the optimal number of vectors). | |
| Feb 16, 2014 at 22:09 | history | edited | Brendan McKay | CC BY-SA 3.0 |
none on 13
|
| Feb 16, 2014 at 6:45 | comment | added | Brendan McKay | @The Mashed Avenger: Yes, that is what I'm doing, together with machinery for eliminating cases equivalent to other cases. Unfortunately the pruning doesn't bite really hard until quite a lot of vectors are present. For example, about 66% of sets of 7 vectors for $n=7$ are acceptable. | |
| Feb 16, 2014 at 6:36 | comment | added | Oleg567 | I am impressed! My previous computations (not very clear) get only $11$ vectors for $n=7$. You obtained $12$. I checked. It vorks. Congratularions! So, we may expect $18$ vectors for $n=10$. | |
| Feb 16, 2014 at 5:17 | comment | added | The Masked Avenger | You may already be doing this, but I'll mention it anyway: in a depth first search, a subset S can be augmented by one of a set V of vectors, the rest having been disallowed for various reasons. As you go deeper, V can get pruned fairly quickly. Knuth used "dancing links" to backtrack quickly; you might use that technique in combination with relations among vectors in V to " preprune ". | |
| Feb 16, 2014 at 4:58 | comment | added | Brendan McKay | @Noam: interesting ideas. If the null space mod 3 is small on average, it might be good to just try all of it. | |
| Feb 16, 2014 at 4:10 | comment | added | Noam D. Elkies | For $s$ vectors $v_i$ it takes about $n \cdot 2^s$ space and $s \cdot 2^s$ time to list all $2^s$ subsums and then sort and check for coincidences. To reduce the factor $2^s$ to $3^{s/2}$ you can write the coincidence as $\sum_{i=1}^s c_i v_i = 0$ with each $c_i\in\{-1,0,1\}$ and then look for coincidences among the vectors $\sum_{i=1}^t c_i v_i$ and $\sum_{i=t+1}^s c_i v_i$ with $t = \lfloor s/2 \rfloor$. In some settings it may be worth doing linear algbra mod $3$ to find a basis for the $3^{s-n}$ vectors $(c_1,\ldots,c_s)$ that work mod $3$ and then try lifting each of them to $\bf Z$. | |
| Feb 16, 2014 at 2:17 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 225 characters in body
|
| Feb 16, 2014 at 0:28 | comment | added | Brendan McKay | Incidentally, Rob Pratt noted the error earlier, but posted it as an answer that was soon deleted. Thanks Rob. | |
| Feb 16, 2014 at 0:13 | comment | added | Brendan McKay | @Oleg567: Thanks. I thought it was suspicious that my program worked immediately. I'll be back! | |
| Feb 16, 2014 at 0:12 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 235 characters in body
|
| Feb 15, 2014 at 19:07 | comment | added | The Masked Avenger | Let $K_n$ count the number of subsets $S$ of $\{0,1\}^n$ so that $S$ has no repeated nonempty subset sum. Is there any good idea of the size of $K_n$? Is this count near the count of maximal such $S$? | |
| Feb 15, 2014 at 16:30 | comment | added | Oleg567 | Take a look at $n=4$. Sums $1001+1110$ and $1010+1101$ are the same: $2111$. I hope you can improve the code. | |
| Feb 15, 2014 at 14:38 | comment | added | rwst | If the numbers 265, 80066 for n=5,6 are confirmed then they don't have it already. | |
| Feb 15, 2014 at 14:32 | comment | added | Per Alexandersson | Something to put on OEIS? | |
| Feb 15, 2014 at 13:45 | history | answered | Brendan McKay | CC BY-SA 3.0 |