how to construct a sequence of positive integers with a unique sum of any contiguous numbers?

For example: 1,2,4,5 has the following sum:

1,2,4,5

3,6,9

7,11

12

and every sum is unique.

Now, 1,2,3 has the following sum:

1,2,3

3,5

6

and apparently not every sum is unique.

Is there any efficient way to generate similar sequence to the first example with the goal of picking every number as small as possible (not just 1,2,4,8,16...)? I understand I could write a program to perha开发者_如何转开发ps bruteforce this, but I'm just curious can it be done in a better way.

---

I think what you're looking for here is a Golomb Ruler. If you take the numbers you're describing above as the distance between marks, you've described a Golomb Ruler. When the set of marks on a ruler has no duplicates, as you've described, that's what makes it a Golomb Ruler.

It appears the standard way to describe a Golomb Ruler is by representing the location of each mark, not the distances between them. Therefore, your 1,2,4,5 would be described as a Golomb Ruler 0-1-3-7-12.

Quoting Wikipedia:

Currently, the complexity of finding OGRs of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NP-hard problem. Problems related to the construction of Golomb Rulers are provably shown to be NP-hard, where it is also noted that no known NP-complete problem has similar flavor to finding Golomb Rulers.

---

Seen <- emtpy set  # Sums seen so far
Open <- empty set  # Sums ending at the last element
for x from 1 to Limit do
    if x in Seen then
        # quick fail
        continue with next x
    end
    # Build new set
    Pending <- empty set
    add x to Pending
    for each s in Open do
        add (s+x) to Pending
    end
    # Check if these numbers are all unique
    if (Pending intersection Seen) is empty then
        # If so, we have a new result
        yield x
        Open <- Pending
        Seen <- Seen union Pending
    end
end

It looks at all sums seen so far, and the sums ending at the last element. There is no need to keep track of starting and ending positions.

If n is the value of Limit, this algorithm would take O(n² log n), assuming set member check and insertion are O(log n), and intersection/union are not slower than O(n log n).

(Though I might be mistaken on the last assumption)

The first few values would be:

1, 2, 4, 5, 8

---

The first 30 values (when selecting always the smallest possible value for the next difference) are

1, 2, 4, 5, 8, 10, 14, 21, 15, 16, 26, 25, 34, 22, 48, 38, 71, 40, 74, 90, 28, 69, 113, 47, 94, 54, 46, 143, 153, 83

These "lexicograpic first" Golomb rulers are less than twice as long as the best known Golomb rulers with up to 30 differences. For most purposes such rulers are sufficient - for signals it just matters that all distances between any two marks are different. Finding the OGR (the optimum Golomb ruler) is rather a mathematical challenge.

@David There is no right or wrong in using one or the other format for describing Golomb rulers. Either is valid, displaying the positions of the marks (0, 1, 3, 7, 12, 20, ...) or the values of the differences. Personally, I prefer the differences for calculations, like @zack does in the question.