How to find a set $R$, such that $R+R=X$ for a given finite set of natural numbers $X$?

Question

Given two finite sets of natural numbers $A$ and $B$, denote the set $\lbrace a+b \mid a \in A \text{ and } b \in B \rbrace$ as $A+B$. What is the best known algorithm of finding a set of natural numbers $R$, such that $R+R=X$ for some finite set of natural numbers $X$?

A brief discussion of this problem is here.

Answer 1

Finding it is a very different question than "the best known algorithm", or the computational complexity of the best algorithm. I don't know much about this, so I'll just state one solution here, which is just the first greedy that comes to mind, in hopes that would help the discussion.

I've tested it with the samples you shared and with some of mine, and it seems to work. This is not efficient at all, but it's a bit unclear if you want the best solution or just one that works.

The pseudo-code is just:

• We have a queue of possible solutions $(n, R_i)$, with $n$ the position that we have read on the original set $X$, and $R_i$ the numbers we've added on the solution set until now.
• We start with the basic pair $(1,\{x_0/2\})$, where $x_0$ is the lowest number in $X$ and must be exactly the lowest number in $R$, $r_0$ multiplied by $2$, so we know that $R$ has to contain $x_0/2$.
• We get a solution $(n, R_i)$ and we execute the single step: we read $X$ as a sorted list, and we read the next number, on position $n$.
  • If it's a number that cannot be made with the ones in $R_i$, then it has to be a new number from $R$, the one producing it. Assume this is the first time that we have seen a sum of this number, then it has to be $r_0 + K$, because the first time a number appears is in a sum with the lowest from $R$. Insert it on $R_i$ and continue reading.
  • If it's a number that can be made with the ones in $R_i$ we have two options: there is overlapping and this is actually the first time a new number appears (so we should include it), or there isn't overlapping and we shouldn't include it. We continue on the second branch, and we add the possibility of the first one as a pair $(n+1, R_i \cup k)$, where $k$ is this new number.

We explore all the possibilities, and if none of them work, then it can't work and we return the empty set. Here it's the solution on Python:

def findingR(l):
    l.sort()
    if(l[0]%2 == 1):
        return []
    else:
        possible_solutions = []
        possible_sums = []
        sums_r = []
        r = [1, l[0]//2] # First number says the position in l of the partial solution
        sums_r.append(r[1]*2)
        possible_solutions.append(r)
        possible_sums.append(sums_r)}

        while(len(possible_solutions) > 0):
            r = possible_solutions.pop(0)
            s = possible_sums.pop(0)
            # We keep reading l from r[0]
            for j in range(r[0], len(l)):
                if(l[j] not in s):
                    r.append(l[j]-r[1])
                    for k in r[1:]:
                        if(l[j]-r[1]+k not in s):
                            s.append(l[j]-r[1]+k)
                else:
                    r_2 = r.copy()
                    s_2 = s.copy()
                    r_2.append(l[j]-r_2[1])
                    r_2[0] = j+1
                    for k in r_2[1:]:
                        if(l[j]-r_2[1]+k not in s_2):
                            s_2.append(l[j]-r_2[1]+k)
                    possible_solutions.append(r_2)
                    possible_sums.append(s_2)
            s.sort()
            if(s == l):
                return r[1:]

        return []

Answer 2

R is a set of integers. Assume R is not empty, otherwise X = empty. Let r be the smallest element of R. Assume r is even, otherwise subtract 1 from each element of R, find X, add 1/2 to each element of X.

Let x be the smallest element of x, then x = r/2 is an integer. Let y be another element of X, then since x+y is an element of R and therefore an integer, y is also an integer. Since y+y is element of R, and an integer, the only numbers that can be elements of X are the even elements of R, divided by 2. Let r’ be the largest element of R, then x’ = r’ / 2 is the largest element of X, therefore r’ must be even, otherwise there is no solution.

If R has one element only then obviously X = { x } is the solution. Otherwise, x + x’ must be an element of R, or there is no solution. If R has three elements, then X = { x, x’ } is the solution; R cannot have just two elements at this point, but has at least four.

We start now with X = { x, x’ } and try adding further elements that are half of an element of R, in increasing order. You only may add the next candidate y if x+y is in R for every x in X. After adding or not adding y all elements of R <= x + y must be the sum of two elements in X.

Answer 3

My first answer at this community, which I will post soon at existing RG discussion (mentioned by the person who asked this Q).

In below proposed Python recipe Set_C will be a nested dictionary...

solution = True
Set_C = {}
Set_MS = set([])
Set_R = set([])

# The truncate() function
def truncate(n, decimals=0) :
    multiplier = 10 ** decimals
    return int(int(n * multiplier) / multiplier)

# Start with some initial subset of the set of natural numbers (X ⊆ ℕ)
print("The initial subset of the set of natural numbers:")
Set_X = sorted(set([4,6,8,10,12]))
print("X = ", Set_X)
print("")

if not 0 in Set_X :
    # Obtaining a set C which will be the candidate for proposed numerical problem
    for x in Set_X :
        if (x%2 == 0) and (not int(x/2) in Set_C) :
            Set_C[int(x/2)] = {'source' : 0, 'destination' : 0}

        if (x%2 == 1) :
            if not truncate(int(x/2)) in Set_C :
                Set_C[truncate(int(x/2))] = {'source' : 0, 'destination' : 0}
            if not truncate(int(x/2))+1 in Set_C :
                Set_C[truncate(int(x/2))+1] = {'source' : 0, 'destination' : 0}

    # Computing the Minkowski sum of set C with itself, i.e. Set_MS = Set_C ⊕ Set_C
    for a in Set_C :
        for b in Set_C :
            Set_MS.add(a+b)

    if sorted(Set_MS) != sorted(Set_X) :
        solution = False
        Set_MS = set([])

    if solution == False :
        # Let perform a trick!
        for s in Set_C :
            for d in Set_C :
                if (s+d) in Set_X :
                    Set_C[s]['source'] = 1
                    Set_C[d]['destination'] = 1
                else :
                    Set_C[s]['source'] = 0
                    Set_C[d]['destination'] = 0

        # Obtaining a set R which will be another candidate for proposed numerical problem
        for c in Set_C :
            if (Set_C[c]['source'] == 1) and (Set_C[c]['destination'] == 1) :
                Set_R.add(c)

        # Computing the Minkowski sum of set R with itself
        for u in Set_R :
            for v in Set_R :
                Set_MS.add(u+v)

        if sorted(Set_MS) != sorted(Set_X) :
            print("There is NO solution for proposed numerical problem.")
        else :
            print("\nThe solution for proposed numerical problem:")
            print("R = ", sorted(Set_R))
    else :
        for c in Set_C :
            Set_R.add(c)
        print("\nThe solution for proposed numerical problem:")
        print("R = ", sorted(Set_R))
else :
    print('This recipe does not allow 0 in set X!')

input("\n\nPress Enter to continue...")