(In reply to
re: Low 300s ?? by broll)
Broll,
This is an interesting theory, and the Golomb Ruler does in fact lead to a set of numbers with no duplicate sums, but your statement in part 3:
"It seems to follow that for any order, x, (here, 20) the last mark on a Golomb Ruler of order (x+1) represents the smallest possible number for which there is at least one (non-randomly selected) subset, S, having the required number of x elements, with no stipulated duplicate."
Has me wondering, how did you arrive at this conclusion? For all values of x <= 12, I have already posted sequences that fail which have EN values lower than those smallest values that you're proposing. In case you missed it, here's an updated list of the sets I've found so far:
x = 4; EN = 5; {1, 2, 3, 5}
x = 5; EN = 8; {1, 2, 3, 5, 8}
x = 6; EN = 13; {1, 2, 3, 5, 8, 13}
x = 7; EN = 21; {1, 2, 3, 5, 8, 13, 21}
x = 8; EN = 25; {1, 2, 3, 5, 9, 15, 20, 25}
x = 9; EN = 35; {1, 2, 3, 5, 9, 16, 25, 30, 35}
x = 10; EN = 46; {1, 2, 8, 11, 14, 22, 27, 42, 44, 46}
x = 11; EN = 58*; {1, 2, 6, 10, 18, 32, 34, 45, 52, 55, 58}
x = 12; EN = 72*; {1, 2, 3, 8, 13, 23, 38, 41, 55, 64, 68, 72}
x = 13; EN = 89*; {1, 2, 3, 13, 22, 28, 43, 50, 57, 73, 81, 86, 89}
x = 14; EN = 108*; {1, 2, 3, 5, 8, 25, 39, 48, 57, 67, 75, 83, 96, 108}
x = 15; EN = 136*; {1, 2, 3, 5, 8, 14, 27, 41, 56, 71, 87, 108, 118, 128, 136}
x = 16; EN = 182*; {1, 2, 3, 5, 9, 16, 26, 31, 43, 61, 70, 79, 116, 132, 163, 182}
x = 17; EN = 214*; {1, 2, 3, 5, 9, 16, 26, 31, 43, 61, 70, 79, 116, 132, 163, 182, 214}
x = 18-20; 246*, 283*, 333*; Golomb Ruler of order x + 1
* denotes best so far, without exhausting all possible combinations.
As the Golomb Ruler discards values that are the same distance apart as other pairs, it throws away a lot of possible combinations for which our failure requirements can be fulfilled. For example the best solution for x = 9 ends with two pairs of values with a distance of 5 between them, and would have been discarded in the corresponding Golomb Ruler. One final note, some of the "rules" can be reduced further when the leading non-zero value is greater than 1. We can decrease all values in the set by the same amount to reduce this value to 1, and still have no duplicate sums. For example, {5, 6, 7, 9, 12}, reduces to {1, 2, 3, 5, 8}. So several of the "rulers" you've proposed had the lowest value of EN could in turn be reduced further, to get a lower value of EN.
Like I said, interesting theory, and I wish it were that simple, but it seems that we're still stuck with the number crunching approach for trying to improve these solutions further.
Edited on July 17, 2010, 2:27 pm
|
|
Posted by Justin
on 2010-07-17 14:24:12 |
re(2): Low 300s ??
