Check if a set of numbers can be produced by continuously halving a single starting number

Question

Given a set of numbers, I want to check if it is possible to produce the full set of numbers by repeatedly splitting one single starting number into its halves and doing the same for each of the halves' halves and so on, and if possible find out what is the smallest possible number to start with that can achieve this.

If a number n to be split is odd, it will split into floor(n/2) and ceiling(n/2) respectively.

e.g. Given set [1, 4, 5], the smallest possible number is 18, as it splits into 9 and 9, which then splits into 4, 5 and 4, 5 respectively. We keep one pair of 4, 5, and split the other pair into 2, 2, 2, 3, and finally 1, 1, 1, 1, 1, 1, 1, 2. Thus, 1, 4, 5 are all obtained.

On the other hand, for set [1, 2, 3, 4, 5, 6], it is impossible to obtain these numbers with any starting number.

How can I efficiently solve this problem? I'm aware that it seems to be some sort of integer partioning problem, but I can't think of any smart way to do this other than straight up brute forcing every number.

Answer 1

I gave this problem a shot and got a first idea which I want to share with you! EDIT: its wrong for case [1,10]!

Given your example set [1,4,5] the answere seems to be 2*9!
(1,4,5 => 2,4,5 => 4,5 => 4+5=9 => 9)

1,2,3,4,5,6 (multiply smaller numbers by 2^n to eliminate "same smaller" ones)
=> 4,5,6 (combine n with n+1)
=> 4+5=>9 5+6=>11
=> 9, 11 not a single number.

Seem to be enough steps. Then i produced this code as it reduces the set and cannot find a single number until it diverges:

import bisect
l = [1, 4, 5]
l.sort()
print(l)
while len(l)>1:
    input()
    smallest = l.pop(0)
    l.insert(bisect.bisect_left(l,smallest<<1),smallest<<1)
    while (len(l)>1 and l[0]==l[1]) or (len(l)>1 and l[0]+1==l[1]): 
        if (l[0]==l[1]): 
            l.pop(0)
        else:
            a = l.pop(0)
            b = l.pop(0)
            l.insert(bisect.bisect_left(l,a+b),a+b)
    print(l)

Now you only need to stop the validator with detected error. My Idea: If length stays same, the distances between some neighbours must fall or we stop when they rise.

Also you can calculate how many numbers are needed to produce the set and multiply the last number accordingly with some *2^n, the first example also gave (2^1)*9! //Edit this was bad, we need to ADD some +/- n to the final number.