1
$\begingroup$

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 $\lfloor \frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$ 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$. 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.

Find the necessary and/or sufficient conditions for a set of numbers to be obtainable via splitting of a single, chosen number, and also how to minimize that number!

$\endgroup$
2
  • 2
    $\begingroup$ Crossposted at MathSE and Stackoverflow. $\endgroup$ Mar 22 at 19:17
  • 4
    $\begingroup$ For the set isn't the smallest possible 17? 17 --> [8, 9] ; 9 --> [4, 5] ; 8 --> [4, 4] ; 4 --> [2, 2] ; 2 --> [1, 1] ; So, you get the set [1, 4, 5] $\endgroup$ Mar 24 at 7:40

0

Browse other questions tagged or ask your own question.